Shortest paths: Dijkstra and Floyd 4
Dijkstra Algorithm
Theory
An important field of application in graph theory is the calculation of shortest paths in graphs. With the help of the Dijkstra algorithm it is possible to determine the shortest way (or optimal solution) from a starting node, over other nodes in between, to the target node.
The algorithm was conceived from the Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959.
The Dijkstra algorithm consists of the following steps:
1. Select starting node as base node
2. Calculate the path length (distance from starting node)to all neighbor nodes of the base node which have not been base node yet.
If the path length is shorter than the shortest path one calculated up to now, the new path and length will be stored.
3. Select that node as new base node that have not been base node yet (consider all, not just neighbors) and that is closest to the starting node.
Is that node the target node (for shortest path) or the very last node (for shortest tree), stop the procedure.
Otherwise continue with step 2.
Example
In the following example, the exact procedures of the Dijkstra algorithm are demonstrated in detail. The nodes represent different places (e.g. cities) and the edges in between illustrate the distances.
Goal: Looking for the shortest path between A and C
First of all, we select the starting node A as the first base node. Then, we have to calculate the path length from starting A to all neighbor nodes of base node A, that have not been base node yet. This step was considered in the column “sequence” (notice, D is not a neighbor node of A).
As demonstrated in the table, the shortest distance is between A and E with distance 2. Consequently, we select E as the new base node.
Now we have to continue with step 2. That means, we calculate the path length (distance from starting node!) from the new base node E to all its neighbor nodes which have not been base node yet. These neighbors which have not been base node yet are B, C and D. Furthermore, calculate the length of these ways. Then, compare the path length with the previous length calculated before. It is not possible to reach B and C over E shorter. Consequently, these two possibilities will no longer be considered, thus they are cancelled and we continue to store the old calculations. A path to D did not exist before, so there is no comparison.
Next (step 3), we choose that node as base node again that has not been base node yet and that is closest to the starting point. A comparison of the distances indicates that node B has a distance of 3 and has not been base node before. So, B is the new base node.
Continue with step 2 again. That means, we calculate the path length (distance from starting node!) from the new base node B to all its neighbor nodes which have not been base node yet. These neighbors which have not been base node yet are C and D. No shorter way to C and D can be reached over B, so that these possibilities are cancelled.
Next, we choose that node as base node again that has not been base node yet and that is closest to the starting point. As we can see, node D has a distance of 6 and was not base node before and is the closest to the starting point (A-C is 10!). Therefore, D is the new base node.
Continue with step 2. The only node which has not been base node before is C. It is also the neighbor node of D. We can reach C over the new base node in two ways: A-E-D-C or A-B-D-C. It becomes clear now that the shortest way to C is: A-E-D-C. C is also the target node and the very last node. So, we have here a shortest tree.
Conclusion: The shortest path from A to C has a distance of 8.
Floyd Algorithm
Theory
The Triple or Floyd Algorithm was first introduced by Robert Floyd in 1962. With the help of this method it is possible to detect the shortest paths between every couple of nodes i and j of a graph G easily. This could also be achieved by determine all optimal trees in the Dijkstra Algorithm, but is way more complicated.
As a first step all ways from an arbitrary node i to another node j leading via node 1 are compared. If this way is shorter, then the old path is replaced by this new value. In the second step all ways via node 2 are chosen. The same procedure is applied in the k'th step with node k.
Algorithmic Model:
Example
The following example should help to understand how to apply the Floyd Algorithm. The graph consists of nodes, edges and numbers. The values inside the nodes display the number of the respective node, the value at the edge the distances between the two nodes.
Firstly, we start with the adjacency matrix, which depicts the original distance values of the direct connection between the respective nodes. The value of the integer variable k indicates the node we can go through as an indirect way. One after one we increase k from 1 to the maximal number of nodes, in our case 5. For each k we create a new table. The coloured cells show the respective cells which aren’t changed.
In the beginning we have the Adjacency Matrix. The cell always contains two numbers. The number above is the respective value of the shortest path. The bottom number is the predecessor node. In our case we have an undirected graph, meaning that the values between the nodes are valid for both directions. This makes the calculation of the shortest path (upper number in the cell) of the tableau easier, because the numbers are symmetric to the diagonal from the left-hand upper corner to the right-hand bottom corner.
For K=1 there are no changes.
If K=2 the way between 4 and 1 and between 5 and 1 shortens as they had the value infinity before. The new value between 4 an 1 is calculated as follows: d (4, 2) + d (2, 1) = 6 + 1 = 7
For the new value between 5 and 1 the same rule applies. The way between 3 and 1 shortens from 4 to 3.
If going through k=3 the tableau does not change.
For K=4 there are no changes.
The same counts for K=5 and the matrix stays the same. This tableau depicts now the optimal solution.
References
H. Müller-Merbach, "Operations Research", 3.Auflage, Verlag Franz Vahlen (1973)
W. Domschke, A Drexl, Einführung in operations research, 6th edition, 2005
W. Domschke, et al., Übungen und Fallbeispiele zum Operations Research, 5th edition, 2005
