Question

Something must be wrong in my understanding of the algorithm. How is it supposed to work on the following graph.

As I understand it, if the starting vertex is (5) then the algorithm would go, 5->4->1 and then terminate. Vertex (2) would still have infinity as it's weight.

from wikipedia:
if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal), then stop. The algorithm has finished.

Graph

Was it helpful?

Solution

No, it would investigate 3 -> 2 after it's done with the 4 -> 1 branch. All children of the currently investigated node are added to the queue, and then from the queue the node with the smallest tentative distance is taken to be processed next.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top