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
How can we compute the shortest-path tree of minimum total weight for a given connected graph?
I am using Dijkstra's algorithm to find the shortest-path tree, but there may exist more than one shortest-path tree with different total weights.
The above picture shows one such example (where $a$ represents the starting vertex).
Is there a way to find the shortest-path tree of minimum total weight without inspecting every possible shortest-path tree?
Dijkstra's algorithm will not allow you to obtain such minimum-weight shortest-path tree due to its greedy nature: once it obtains the shortest path to a vertex, the algorithm never reconsiders this vertex again.
One possible approach to obtain such a tree is to apply a small extension to Bellman–Ford's algorithm. Whenever there is a tie in step 2 of the algorithm $-$ that is, whenever there is a tie between (1) a newly computed distance between the starting vertex $s$ and a vertex $v$, and (2) the current best shortest path between $s$ and $v$ $-$ compute how much weight each of the two shortest path candidates adds to the current tree (and keep the path that minimizes this value). The current tree is available in the predecessor array, which stores the tree as an array of parent pointers.
Applying the above solution, you are, in effect, checking all possible shortest paths, so I presume that the answer to your last question is no.
The minimum-weight shortest-path tree can be computed efficiently [1].
The shortest-path subgraph in a rooted, weighted, directed graph is obtained from the graph by removing those edges $(u, v)$ not on any shortest path from the root — those for which $D_{T_S}(r, u) + w(u, v) > D_{T_S}(r, v)$. It is easily shown that paths from $r$ in the shortest-path subgraph correspond to shortest paths from $r$ in the original graph, and vice versa.
Proof. Call the original graph $G = (V, A)$ and the shortest-path subgraph $G' = (V', A')$.
Let $(v_0, v_1, \dots, v_k)$ be a path from $v_0 = r$ to $v_k = v$ in $G'$. If $k = 0$ then the path contains no edges and is thus trivially a shortest path in $G$. For $k > 0$, if all paths of length $k - 1$ from $r$ in $G'$ correspond to shortest paths from $r$ in $G$, then in particular $(v_0, v_1, \dots, v_{k - 1})$ is a shortest path from $r$ to $v_{k - 1}$; that is, $\sum_{i = 1}^{k - 1} w(v_{i - 1}, v_i) = D_{T_S}(r, v_{k - 1})$. If our path to $v$ is not a shortest path then $$ D_{T_S}(r, v) < \sum_{i = 1}^k w(v_{i - 1}, v_i) = \sum_{i = 1}^{k - 1} w(v_{i - 1}, v_i) + w(v_{k - 1}, v_k) = D_{T_S}(r, v_{k - 1}) + w(v_{k - 1}, v). $$ This contradicts the assumption that $(v_{k - 1}, v) \in A'$. Since $(v_0, v_1, \dots, v_k)$ was an arbitrary length-$k$ path, this shows by induction that paths from $r$ in $G'$ correspond to shortest paths from $r$ in $G$.
Conversely, let $(v_0, v_1, \dots, v_k)$ be a shortest path from $v_0 = r$ to $v_k = v$ in $G$. If $k = 0$ then the path contains no edges and is thus trivially a path from $r$ in $G'$. For $k > 0$, if all shortest paths of length $k - 1$ from $r$ in $G$ correspond to paths from $r$ in $G'$, then in particular $(v_0, v_1, \dots, v_{k - 1})$ is in $G'$; that is, $(v_{i - 1}, v_i) \in A'$ for all $i \in \{1, 2, \dots, k - 1\}$. Thus if our path to $v$ is not in $G'$ then it must be the case that $(v_{k - 1}, v) \notin A'$, so $$ \sum_{i = 1}^k w(v_{i - 1}, v_i) = \sum_{i = 1}^{k - 1} w(v_{i - 1}, v_i) + w(v_{k - 1}, v_k) = D_{T_S}(r, v_{k - 1}) + w(v_{k - 1}, v) > D_{T_S}(r, v). $$ This contradicts the assumption that $(v_0, v_1, \dots, v_k)$ is a shortest path in $G$. Since this was an arbitrary length-$k$ shortest path, this shows by induction that shortest paths from $r$ in $G$ correspond to paths from $r$ in $G'$.
A branching in a rooted, directed graph is a spanning tree with all edges directed away from the root. Efficient algorithms for finding minimum-weight branchings are known [2].
This specifically refers to an implementation of Edmonds' algorithm using Fibonacci heaps.
Thus, finding a minimum-weight shortest path tree in a directed graph reduces to finding a minimum-weight branching in the shortest-path subgraph. To find the minimum-weight shortest path tree in an undirected graph, simply direct it: duplicate each edge, directing one copy of each endpoint. Shortest-path trees in the original graph, directed appropriately, then correspond to shortest-path trees in the directed graph.
