Shortest paths with Dijkstra's Algorithm

Calculating paths, too

Let's run the algorithm again in our graph:

This time, however, let's keep track of the actual shortest paths. They all begin empty, except for the path of the initial node, which simply contains it:

path to A = empty
path to B = empty
path to C = C
path to D = empty
path to E = empty

The new thing is that we will update those paths every time we modify the minimum distance of a node.

Let's check the neighbours of our current node. Let's begin with B. We add 0 + 7 = 7. As that value is less than infinity, we change the minimum distance of B with it and replace the current path to B with the path to the current node (path to C, which is C), plus B. This means that path to B = C, B.

We repeat the procedure with neighbours A and D. After that, our graph and paths are as follows:

path to A = C, A
path to B = C, B
path to C = C
path to D = C, D
path to E = empty

Our current node is now set to A. We check its only non-visited neighbour, B. As we replace the minimum distance of B from 7 to 4, we also replace its current path with the path of the current node A (C, A), plus B: path to B = C, A, B).

path to A = C, A
path to B = C, A, B
path to C = C
path to D = C, D
path to E = empty

We mark A as visited and select our next current node: D. We check two neighbours: B and E.

When checking B, we don't replace its minimum distance (as the existing 4 is less than the calculated 7), so we don't replace its current path, either. Remember: we only replace a path when we modify the minimum distance of a node.

We then check neighbour E, update its minimum distance (9, which is less than infinity) and path (path to E = C, D, E, which is the path to D plus E), and are left with this:

path to A = C, A
path to B = C, A, B
path to C = C
path to D = C, D
path to E = C, D, E

Let's fast-forward a bit: we continue applying the algorithm until we're done. After we finish, our graph and paths will be the following:

path to A = C, A
path to B = C, A, B
path to C = C
path to D = C, D
path to E = C, A, B, E

Congratulations! Those are the minimum paths between C and every other node!