# Shortest paths: 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!