A Random Image
Dijkstra's algorithm - An Illustrated Explanation
I was recently doing some reading on algorithms, as I was reading up on Dijkstra's algorithm, I noticed that there seemed to be a lack of nice explanations out there. I found lots of applets, and demonstrations, but none of them had a step-by-step explanation, i.e. why certain events were occuring. Wikipedia has an article on Dijkstra's Algorithm, but personally, I didn't find it to clear. I decided to put up my own effort at explaining the algorithm, if any of it is unclear, let me know and I'll add in more detail, or a better explanation.
Dijkstra's Algorithm
Before I start into how Dijkstra's Algorithm does what it does, here is a short description of what Dijkstra's Algorithm does:
In a given graph, and starting node, Dijkstra's Algorithm discovers the shortest path from the starting node to all other nodes.
Assumptions: The cost/length of travelling between nodes is known.
The Explanation: Dijkstra's Algorithm
Figure 1: Dijkstra - Initial Position
Figure 1 displays the graph: nodes are black circles labelled a-f, a path is a black line connecting two nodes, each path has an associated length beside it (the numbers). The lengths are not to scale.
Node 'a' is our starting node, we want to find the shortest path to all other nodes in the graph. To do this, we generate a table. This table has the distance to all the nodes in the graph, from the perspective of the starting node 'a'.
| Node | Distance to Node from Node 'a' |
|---|---|
| b | INFINTE |
| c | INFINTE |
| d | INFINTE |
| e | INFINTE |
| f | INFINTE |
| g | INFINTE |
| h | INFINTE |
| i | INFINTE |
As can be seen from Table 1, the initial entries for the distances are all set to infinity (or some notional maximum value). This ensures that any path found will be shorter than the initial value stored in the table.
The node 'a' is the starting node, as such we examine all the possible paths away from this node first. The options are as follows:
| Node | Distance to Node from Node 'a' |
|---|---|
| b | 7 |
| c | 4 |
| d | 5 |
These values are used to update the graph table, Table 1, which becomes:
| Node | Distance to Node from Node 'a' |
|---|---|
| b | 7 |
| c | 4 |
| d | 5 |
| e | INFINTE |
| f | INFINTE |
| g | INFINTE |
| h | INFINTE |
| i | INFINTE |
Figure 2: Dijkstra's algorithm
Figure 2 shows the routes marked in red. We know have three paths from node 'a'. However, these paths are not yet guaranteed to be the shortest path. To be sure we have the shortest path, we have to keep going.
The next move in the algorithm is to move to the nearest node from node 'a'. In this case that is node 'c'.
Figure 3: Dijkstra's Algorithm
At node 'c' we have paths available to nodes 'b' and 'h'. When calculating the distances we have to calculate the distances from node 'a'. In this case that means the following:
| Node | Distance to Node from Node 'a' |
|---|---|
| b | 6 |
| h | 13 |
These values are then compared to the values stored in the Table 3. It can be seen that both of these values are less than the current values stored in the table, as such table 3 becomes:
| Node | Distance to Node from Node 'a' |
|---|---|
| b | 6 |
| c | 4 |
| d | 5 |
| e | INFINTE |
| f | INFINTE |
| g | INFINTE |
| h | 13 |
| i | INFINTE |
This step has illustrated one of the advantages of dijkstra's algorithm: the route to node 'b' is not the most direct route, but it is the shortest route; Dijkstra's Algorithm can find the shortest route, even when that route is not the most direct route.
Figure 4: Dijkstra's Algorithm
Again, all paths accesible from node 'c' have been checked, and the table of paths has been updated. Node 'c' is marked as visited.
IMPORTANT:
- A Visited node is never re-visited.
- Once a node has been marked visited, the path to that node is known to be the shortest route from the initial node.
In that case, we should add another column to our table:
| Node | Distance to Node from Node 'a' | Visited |
|---|---|---|
| b | 6 | NO |
| c | 4 | YES |
| d | 5 | NO |
| e | INFINTE | NO |
| f | INFINTE | NO |
| g | INFINTE | NO |
| h | 13 | NO |
| i | INFINTE | NO |
As these value are being updated, the route that accompanies these distances also needs to be stored.
Once again, the table of paths is consulted, and the shortest path to a node that has not been visited is found. This node becomes the next current node. In this case, that is node 'd'.
Figure 5: Dijkstra's Algorithm
From node 'd', the following paths are available:
| Node | Distance to Node from Node 'a' |
|---|---|
| f | 14 |
The table of all paths is updated to reflect that, and the node 'd' is marked as visited, this locks in the shortest path to node 'd' also:
| Node | Distance to Node from Node 'a' | Visited |
|---|---|---|
| b | 6 | NO |
| c | 4 | YES |
| d | 5 | YES |
| e | INFINTE | NO |
| f | 14 | NO |
| g | INFINTE | NO |
| h | 13 | NO |
| i | INFINTE | NO |
It can be seen from table 8 above, that the next nearest node to node 'a' is node 'b'. All paths from node 'b' are examined next. In this instance, we have a path to a node that is marked as visited: node 'c', we already know that the path to node 'c' is as short as it can get (the node being marked as visited is the marker for this).
Figure 6: Dijkstra's Algorithm
As figure 6 shows, we check the path the only other node accesible from node 'b': node 'e'. This updates our paht table as follows:
| Node | Distance to Node from Node 'a' | Visited |
|---|---|---|
| b | 6 | YES |
| c | 4 | YES |
| d | 5 | YES |
| e | 31 | NO |
| f | 14 | NO |
| g | INFINTE | NO |
| h | 13 | NO |
| i | INFINTE | NO |
Table 9 again tells us that the next node for us to visit is node 'h'.
Figure 7: Dijkstra's Algorithm
We add up the paths, and mark the nodes as visited...
Figure 8: Dijkstra's Algorithm
We keep on doing this....
Figure 9: Dijkstra's Algorithm
Until all the nodes have been visited!
Every step in this process can be viewed in this gallery: Dijkstra's Algorithm - Step-by-Step
Comments
Nice tutorial, but one question:
Looking at the final graph, how do you then determine the shortest path from A to F?
Route from A to F
OK.. so if you are trying to find the shortest route from A to F: The nodes visited would go in this order:
A - C - D - B - H - F. At this point the algorithm would stop, knowing that the shortest route to Node F is A - D - F. Now, the interesting thing in this route to note is this: that route was discovered as soon as node 'D' was visited, this is the third node that was checked. But, it is not guaranteed to be the shortest path until the node in question has been marked as visited also.
The reason for this is because you cannot know for sure that you have travelled every path to a node until it has been marked as visited.
Let us assume that the cost of travelling between C - H is 6, and the cost of travelling between H - F is 1. In this situation the shortest route from A to F is A - C - H - F. But, this route will not be discovered until after A - D - F (because D is checked before H). In this case, the first route found to F will be A - D - F, at a cost of 14. Whereas A - C - H - F is a cost of 11.
The most important point to remember is this: Once a node is visited, we KNOW that there cannot be a shorter path to that node (from the origin). This is because we always visit the next nearest node from the origin. That means that at every step along the way, it has to be longer to go via any other route.
I know this is a little bit circuitous in its reasoning. It's important to remember that algorithm finds the shortest route from a given point, and all distances are relative to that point. As can be seen, the algorithm does not guarantee that it finds the shortest route first, just that it finds the shortest route.
...
It looks like you are a true expert. Did ya study about the topic? hrhr
hey dat was nice
wat i wish to say is dat in while programming dijkstra how will we back track like in the above example we backtracked for findin path of node e...i,e, from a to c and then to e....i mean for finding the shortest path i will have to try all possible combinations of visited nodes...dats too cumbersome to program...
Post new comment