Graph shortest path confusion

Question

I want to calculate the shortest path from A to F in this graph

Following Dijkstra's algorithm I reach E and then go to C, but then I can't comeback to E, how do I solve this?

My steps were:

• All cost to infinity but a, that I've set to 0.
• From A I've updated b and c, considering b had a 26 cost, I went to b.
• Then d, e and finally c

Answer 1

It sounds like you’re taking the shortest path from wherever you find yourself currently, and not calculating the total distance to get to a node. Let’s step through it in detail.

Dijkstra’s algorithm sets up two sets of nodes: visited (with known distances) and unvisited (with tentative distances). We start with:

visited: { }
unvisited: { a(dist 0), b(dist ∞), c(dist ∞), d(dist ∞), e(dist ∞), f(dist ∞) }

The smallest tentative distance becomes permanent, and that node is the “current” node. Using the current node, we update the tentative distances that the current node can reach in a shorter distance and mark the current node as visited:

visited: { a(0) }
unvisited: { b(26), c(50), d(∞), e(∞), f(∞) }

We repeat the above paragraph, making the shortest tentative distance permanent, and updating tentative distances that the current node can reach in a shorter distance and mark the current node as visited:

visited: { a(0), b(26) }
unvisited: { c(50), d(91), e(∞), f(∞) }

And again:

visited: { a(0), b(26), c(50) }
unvisited: { d(91), e(76), f(∞) }

This time, we pick e as the current node, because its tentative distance is less than d’s. But d’s tentative distance doesn’t get updated, because we’ve already found a better distance. Mark e visited:

visited: { a(0), b(26), c(50), e(76) }
unvisited: { d(91), f(101) }

Now d is current, but it doesn’t update any distances (we don’t need to look at visited nodes, we’ve already found the best distances there). So we just mark it visited:

visited: { a(0), b(26), c(50), e(76), d(91) }
unvisited: { f(101) }

Now f is current, which means we’re done.