# Shortest paths with Dijkstra's Algorithm

Racso
443.4K views

## 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!