CODEWITHSUNDEEP
algorithm
stevenpcurtis
stevenpcurtis

Reputation: 2001

Dijkstra step-by-step

I've been following Dijkstra's algorithm step by step from http://www.ifp.illinois.edu/~angelia/ge330fall09_dijkstra_l18.pdf

However with my own example, I don't find the shortest path if I stop as soon as I reach the destination node.

I'm going to look for the shortest path from A -> E as below:

enter image description here

And I traverse as follows:

enter image description here

This gives me the shortest path of A->F->E which is incorrect (the shortest path is C->D->E).

The difficulty being that I never inspect D.

But I've read (not least in the link above) that you can stop inspecting nodes as soon as you reach the destination. How is this true?

Upvotes: 0

Views: 172

Answers (1)

Henry
Henry

Reputation: 43738

You stopped too early. Continue the algorithm until E is selected as the current node.

Upvotes: 1

Related Questions