Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I was wondering if the output of an algorithm like Dijkstra was always contained in the minimal spanning tree, however, a counter example to this claim are cyclic graphs like:
The shortest path $B \rightarrow C$ is in no way contained in the MST. Are there known conditions on the graph and the edge weights that ensure that all vertex-to-vertex shortest paths are contained in the minimum spanning tree?
A basic observation first: in any unweighted graph with a cycle, there is an MST that is not a shortest path tree for some source node. Proof: the tree must omit some edge on the cycle, and for either endpoint of that edge, the shortest path tree contains the edge. So if we fix the source node for the SSSP tree, then it'll be difficult to say more than that the SSSP tree and the MST are equal for graphs that are trees themselves.
Raphael mentions in a comment that the same argument holds for weighted graphs with triangle inequality; to adapt the argument, we only need to consider the lightest edge on that cycle.
Generalizing in a different direction, whenever you have a weighted graph with weight function $w > 0$ that doesn't have a unique MST, then for every MST there is some node for which the MST is not a shortest path tree. The proof will assume that all edge weights are positive; I originally thought that since the set of MSTs is invariant under adding the same value to all edge weights, this would show the result for general graphs, but it doesn't since the set of shortest path trees is not invariant under that operation. Thus, the result will only be proven for graphs with positive weights. Regarding notation, $w > 0$ means that $w$ is positive everywhere.
Proof: Take two different MSTs $S = (V, E_S)$ and $T = (V, E_T)$ of some graph $G = (V,E)$. Consider a lightest edge that is in $S$ but not $T$, that is $ \{u,v\} = e \in \arg \min \{w(f): f \in E_S \setminus E_T\}$. Take the unique $u-v-$path $p_{u,v}^T \subseteq E_T$ in $T$. We know $e \not \in p_{u,v}^T$. Note also that $|p_{u,v}^T| \geq 2$.
Any two MSTs have the same multiset of edge weights, see e.g. Raphael's proof here; due to this, the weight of the lightest edge in $E_S \setminus E_T$ is the same as that of the lightest edge in $E_T \setminus E_S$. Now take all edges on $p_{u,v}^T$ that are not in $S$, that is $\Delta = (p_{u,v}^T \setminus E_S) \subseteq (E_T \setminus E_S)$. We know that $\Delta \neq \emptyset$ since otherwise, $\{e\} \cup p_{u,v}^T$ would be a cycle in $S$. Any lightest edge in this difference, $e' \in \arg \min \{w(f): f \in \Delta\}$, satisfies $w(e) \leq w(e')$ due to the choice of $e \in \arg \min \{w(f): f \in E_S \setminus E_T\}$. Since all edge weights are positive and $|p_{u,v}^T| \geq 2$, we know that $w(e) \leq w(e') < w(p_{u,v}^T)$. Thus, $T$ is not a shortest path tree for $u$. $\square$
