Shortest paths: Dijkstra and Floyd 4: Unterschied zwischen den Versionen

Version vom 1. Juli 2013, 19:03 Uhr

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: