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

Version vom 1. Juli 2013, 18:39 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).

Datei:Jh1.png

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.