CODEWITHSUNDEEP
algorithmgraph-algorithm
Justin
Justin

Reputation: 4216

Dijkstra's Algorithm termination

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

Upvotes: 2

Views: 1892

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183968

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.

Upvotes: 3

Related Questions