Let $G = (V, E)$ be a graph, and $s \in V$. We say that a spanning tree $T$ is of $s$-efficient if for all $v \in V$, $d_T(s, v) = d_G(s, v)$, where $d_X(a, b)$ counts the number of edges in a shortest path between $a$ and $b$, in a graph $X$. Let $\mathfrak{T}_s(G)$ be the set of all $s$-efficient spanning trees of $G$.
Let $w: E \to \mathbb{R}$, and naturally extend it to subgraphs via $W(X) = \sum_{e \in X} w(e)$. I want to find $\arg\min_{\mathfrak{T}_s(G)} W$. That is, an $s$-efficient spanning tree of $G$ of minimum sum of weights. Note, the notion of $s$-efficient does not look at any edge weight, it only cares about number of edges.
I want to do this in time $O(|V| + |E|)$.
Here's what I've thought:
1) Find the set of edges E' that are in some s-efficient tree:
Compute d[v] = d_G(s, v) for all v, via BFS.
Add an edge {u, v} to E' when d[u] = d[v] + 1, or d[v] = d[u] + 1.
2) Find a minimum spanning tree of G' = (V, E'):
Perform a BFS on G'.
When we pop a vertex $u$ and see its neighbor $v$, we keep the lightest edge incident to $v$.
Alternatively, step 2 can be written as:
2) Hang each vertex off the lightest edge in $E'$ for which it's the target.
t[v] = null for all v in V
For each e = {u, v} in E':
// Assume wlog d[v] = d[u] + 1.
if t[v] is null or w(t[v]) > w(e):
t[v] = e
Return {t[v] | v in V}.
It's not clear to me that part 2) produces a minimum spanning tree for G'. Specifically, we have to use some property of $E'$, since this would otherwise yield a linear time minimum-weight spanning tree algorithm, by setting $E' = E$.
- Is this algorithm correct? Why?
- If (as I suspect) it's not, is there an algorithm with an $O(|V| + |E|)$ running time?