patternMinor
Minimum-weight shortest-path tree
Viewed 0 times
pathshortestweightminimumtree
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#68862, answer score: 3
Revisions (0)
No revisions yet.