Dijkstra's algorithm: an example

Let say you have some nodes (airports, routers, cities, etc) and you know the costs of moving from any node to its directly connected neighbors. You would like to know the best way (where "the best" is defined as the least expensive) from certain node to any other node.
One way to achieve this is to follow Dijkstra's algorithm, which we will demonstrate in this article.
Before we start, couple of notes:

1. In general, the cost of the link that directly connects two neighbors is not the same in both directions - Dijkstra's algorithm assumes that links between the nodes are unidirectional. However, for simplicity, in our example costs in both directions ARE the same.
2. It is possible that there is no path at all between some nodes. But if there is no path between node X and node Y, then there is no path between node X and any node Z that is connected to Y (otherwise, you could get from X to Y through Z). In other words, you have islands of connectivity. Dijkstra's algorithm will tell you that cost from X to Y is infinity, but again we will not consider this in our example.

So let's start. We are at node A and would like to know the minimum cost to all the other nodes.

 

1. We will create a shortest path tree that leads from A to all the other nodes. The A is the root of that tree. The cost to get from A to A is 0. 

 

2. Take in consideration all the nodes directly connected to A. For each node, calculate the distance from A. In this iteration, the distance is simply the cost of the link from A to that particular node.

 

3. From the three nodes we added in the previous step, the node with the best cost is B. B is on the path, and we are done with B: the minimum cost to get from A to B is 5. 

 

4. Keep the links to C and D in the graph, but also add all the nodes that B is directly connected to (and which are not already in the graph). In other words: add the node E.

For each of the new nodes, the “current cost” is the cost from A to B (5) PLUS the cost from B to that particular node. If the node is already in the graph, but it is cheaper to get to it through B, delete the old connection and add the new one (see the new connection to D). Otherwise, the new link is not added.

 

5. Now again we need to pick the node which is the closest to A. In this iteration, that's D.

 

6. Let’s add all the nodes D is connected to and review D’s links to them. Actually, other than B, D is connected to C and E, which are already in the drawing.
The cost from A to E through B and D is 15, which is more than what we already have for E (13).
The connection to C is more interesting: the current cost to C is 12, and the cost through B and D is also 12. We could discard the new path, as it doesn’t give us lower cost from what we already have. However, if 12 indeed becomes the lowest cost to C, it may be useful to know that we can get there via multiple paths. To keep the diagram simple, we take the first approach.
One way or another, we again have to pick the node with the shortest path to A. In this case it’s C.

7. C is connected to F which is the last node in our example. The current cost to F will be cost to C (12) plus the cost from C to F (also 12).

8. Almost finished… There are only two nodes to choose from: E with distance of 13 and F with distance of 24. Obviously, node E is the winner.

 

9. We have added E to the shortest path tree, so now we have to consider all the E’s links – and that’s only the link from E to F. Given that the cost from A to F through E is 23 (13 + 10), and the current cost from A to F through C is 24, we will replace the temporary link from C to F with the permanent from E to F.

 

10. At the end of the exercise, we have description of shortest path from A to all the nodes in the diagram. We also have associated cost for every path.