If there exists a weighted graph G, and all weights are 1, what would Dijkstra's algorithm return as the shortest paths from a given node?
If the weights of all branches in the graph were equal to 1, what would Dijkstra's algorithm return as the shortest paths from a given node?
Viewed 28
1 Answers
A correct implementation of Dijkstra's algorithm will return, for every node, the 'predecessor' node. If you follow the predecessor nodes in sequence you will get back to the given node on a path that goes over the fewest number of connections.
Related