4
$\begingroup$

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.

Shortest-Path Tree

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?

$\endgroup$
  • $\begingroup$ How many trees does Dijkstra's algorithm give you? $\endgroup$ – Yuval Filmus Jan 17 '17 at 17:09
  • $\begingroup$ The algorithm gives only one tree(depending on which shortest path is chosen in case of multiple shortest paths between the source and vertex) but there is no gurantee that the tree is of least possible weight. $\endgroup$ – Addy101 Jan 17 '17 at 17:15
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

References

[1] S. Khuller, B. Raghavachari, and N. Young. Balancing minimum spanning trees and shortest-path trees. Algorithmica, 14(4):305–321, Oct 1995.

[2] H. N. Gabow, Z. Galil, T. Spencer and R. E. Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, 6 (2), pp. 109-122, (1986).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.