Dijkstra's algorithm

The algorithm of Dijkstra ( Edsger W. Dijkstra after its inventor ) is an algorithm from the class of greedy algorithms and solves the problem of shortest paths for a given start node. It thus calculates a shortest path between the starting node and given one of (or all) of the remaining nodes in an edge -weighted graph. The edge weights of the graph must not be negative. For graphs with negative weights of the Bellman - Ford algorithm is suitable.

For incoherent undirected graphs the distance to those nodes is infinite, where there is no path from the start node. The same is true for directed not strongly connected graphs.

Algorithm

Informal presentation

The basic idea of the algorithm is to always follow that edge that promises the shortest stretch from the start node. Other edges are only pursued if all shorter sections were observed. This approach ensures that, when a node a shorter path may exist to him. Once a calculated distance between the start node and a node reached is not changed. This procedure continues until the distance of the target node was calculated (single- pair shortest path ) or the distances of all nodes are known to the start node ( single-source shortest path ).

The algorithm can be described by the following steps. Are calculated both the shortest paths and their consequences node.

In this way, the algorithm calculates, starting from a start node the shortest paths to all other nodes. If you, however, only on the path to a specific node interested, then, in step ( 2) already stop if the search node is the active one.

Due to the property, fails to alter fixed distances to the start node, Dijkstra's algorithm is one of the greedy algorithms that favor the currently most promising partial solution in each step. Unlike some other greedy algorithms, however, Dijkstra's algorithm computes the optimal solution. This feature is based on the assumption that the shortest routes between nodes part together form the shortest route to a path to the path. Assuming positive edge weights, the assumption is valid, because you would find later a shorter path from the start node to a destination node, one would have even the shorter leg earlier must examine to execute the algorithm correctly. Then you would have the shorter leg of the destination node found earlier than on the longer path.

However, this assumption is no longer true if the graph contains negative edge weights. Then each leg can indeed be a shortest path between the endpoints for yourself, you could improve the overall distance but over a longer partial path if a negative edge reduces the path length again. In the image to the nodes 1, 2, 3 and 4 of Dijkstra's algorithm would find the shortest path from 1 to 3 over 2 because the step to a total of 4 is already longer than the entire upper path. The negative edge effects but that the lower path is shorter.

Algorithm in pseudocode

The following lines of pseudo-code describing a feature called Dijkstra, who receives a graph and a starting node in the graph as input. The start node specifies the node, are being sought by the shortest of the distances to all nodes. The result is a list indicating for each node v the predecessor node on the path from the start node to v.

The graph consists of nodes and weighted edges between its nodes. If there is an edge between two nodes, so they are each neighbor. The weight edges between adjacent nodes u and v is given in pseudo-code as abstand_zwischen (u, v).

First, the distances and predecessors are initialized depending on the graph and start node. This is done in the method initialize. The actual algorithm used a method distanz_update which performs an update of the distance if a shorter path is found.

1 function Dijkstra ( Graph, source node ):   2 initialize ( graph, start node, distance [] predecessor [ ], Q)   3 while Q is not empty: / / The actual algorithm   4 u: = node in Q with smallest value in range [ ]   5 remove u from Q / / u for the shortest path is now determined   6 for each neighbor v of u:   7 if v in Q:   8 distanz_update (u, v, distance [] predecessor []) / / check distance from the start node to v   9 return predecessor [ ] Initialization resets the distances to infinity and the predecessor as unknown. Only the start node has distance 0 The set Q contains the nodes to which no shortest path has been found.

1 Method initialize ( graph start node distance [] predecessor [ ], Q):   2 for each vertex v in Graph:   3 distance [v ]: = infinity   4 predecessor [v ]: = null   5 range [ start node ]: = 0   6 Q: = the set of all nodes in Graph The distance from the start node to node v is shortened if the path to v via u shorter than the previously known way. Accordingly, u the predecessor of v on the shortest path.

1 Method distanz_update (u, v, distance [] predecessor []):   2 alternative: = distance [u ] abstand_zwischen (u, v ) / / path from the start node to v via u   3 if alternatively < distance [v ]:   4 distance [v ]: = alternative   5 predecessor [v ]: = u If one is only interested in the shortest path between two nodes, you can let cancel after line 5 of the Dijkstra function the algorithm if u = target node.

The shortest route to a destination node can now be determined by iterating over the predecessor:

1 erstelleKürzestenPfad function ( destination node, predecessor []) 2 Way []: = [ destination node ] 3 u: = target node 4 as long as predecessor [u ] is not null: / / The predecessor of the start node is null 5 u: = predecessor [ u] 6 add u to the beginning of Route [ ] 7 return path [ ] implementation

Nodes and edges between nodes can usually be represented by matrices or pointer structures. Also on the predecessor of a node can be a pointer reference. The distances of the nodes may be stored in boxes.

For efficient implementation, the amount Q of the nodes for which no shortest path has been found to be implemented by a priority queue. The elaborate initialization takes place only once, but the repeated hits on Q are more efficient. As the value for the node its respective distance is used, which is given in pseudo-code with distance [v ]. Shortens the distance, a partial reordering of the queue is needed.

As a data structure for this purpose is a Distance Chart or an adjacency matrix.

Example

An example of the application of the Dijkstra algorithm is a search for a shortest path on a map. In the example used here will be found in the map of Germany shown below, a shortest path from Frankfurt to Munich.

The numbers on the connections between two cities give each case the distance between the two at the edge connected cities. The numbers after the city name indicate the calculated distance of the city to the start node Frankfurt, oo stands for ∞, ie for unknown distance. The light gray shaded nodes are the nodes whose distance is relaxed ( ie is shortened if a shorter path is found), the dark gray shaded nodes are those for which the shortest path from Frankfurt is already known.

The selection of the nearest neighbors according to the principle of a priority queue. Relaxed therefore require the use of reordering.

• Example

Distances from the start node (Frankfurt) determine (relax), re-order the priority queue Q ( 1 Mannheim, Kassel 2nd, 3rd Würzburg, ...)

Mannheim is the closest node, relax with neighboring nodes Karlsruhe, next predecessor of Karlsruhe is now Mannheim, reorder Q ( 1 Karlsruhe, Kassel, 2, 3, Würzburg, ...)

The starting point of closest node to be examined according to Q is now Karlsruhe, relax with Augsburg, reorder Q ( 1 Kassel, Würzburg 2nd, 3rd Augsburg, ... )

Closest to be examined node is now Kassel, relax with Munich, reorder Q ( 1 Würzburg, 2 Augsburg, Munich 3, ...)

Closest to be examined node is now Würzburg, relax with Erfurt and Nuremberg, reorder Q ( 1 Nuremberg, Erfurt 2, 3, Augsburg, Munich, 4, ...)

Closest to be examined node is now Nuremberg, relax with Munich and Stuttgart, reorder Q ( 1 Erfurt, Augsburg 2, 3, Munich, Stuttgart, 4, ...)

Closest to be examined node is now Erfurt, relax with anyone, reorder Q ( 1 Augsburg, Munich 2, 3, Stuttgart, ...)

Closest to be examined node is now Augsburg, relax with Munich, reorder Q ( 1 Munich, 2.Stuttgart )

Destination node to be examined: Shortest way to Munich is now known; Reconstruction using erstelleKürzestenPfad (). This is Frankfurt -Würzburg -Nuremberg- Munich.

Basic concepts and relationships

An alternative algorithm for searching shortest paths, the other hand, based on the optimality principle of Bellman, is the Floyd - Warshall algorithm. The optimality principle states that, if the shortest path from A to C via B, the partial path AB must also be the shortest path from A to B.

A further alternative algorithm, the A * algorithm, the Dijkstra's algorithm to the enhanced one estimator. If this certain properties satisfied in order to the shortest path can be found more quickly under certain circumstances.

Calculation of a spanning tree

After the end of the algorithm, a spanning tree of the component of shortest paths from of π is listed on all nodes of the component in the predecessor pointers. However, this tree is not necessarily minimal, as the picture shows:

Be a number greater than 0 minimum spanning trees are covered either by the edges and or and if. The total cost of a minimum spanning tree, be. Dijkstra's algorithm provides a starting point with the edges and as a result. The total cost of this spanning tree be.

The calculation of a minimum spanning tree is possible using the algorithm of Prim or Kruskal 's algorithm.

Time complexity

In the following, the number of edges and the number of nodes.

The time complexity of the algorithm depends largely on the data structure used to store the unvisited node ( Q). Normally, one will use here a priority queue by utilizing the node where the elements with their respective current distance as the key / priority.

Looking at the algorithm from this point results in the following costs:

The "filling" of Q on line 02 is achieved by inserting each node as well as its priority ( = distance) by insert into the queue; that is, since there are a total of node is performed once.

As will be removed in line 04 one node of Q (or the queue), it follows that the loop is also traversed in row 03 times ( possibly an earlier aborted due to reaching the target node is included here ). In each loop must be checked whether the queue is ( empty, line 03 ) is empty, and it must be the next element with the lowest priority are removed ( extractMin, line 04); the two operations are therefore carried out each time.

Although the number of calls to the relax function, for each iteration of the loop vary in row 07 ( since the number of each node u outgoing edges can be naturally different ), the loop is seen in total over the life time of the entire algorithm but run time because each node is only considered once, and thus each edge emanating from it can also be considered only once. It all outgoing edges of all nodes will thus be reviewed in the graph, and so of course you get all the edges of the graph, ie piece.

If here, reduce the previously calculated distance of the node v, of course, the priority in the queue by decreasekey must be reduced accordingly. This happens in the worst case ( in the - unlikely - event that the verification of each edge provides a shorter path ) at most times.

For completeness, we should also consider the setting of d [ v] and π [v ] in the relax function also, but this can be achieved in constant time with each of complexity.

Generally speaking, therefore a complexity of.

Would you simply use to manage the node now such as a list, would that have a term of; insert, empty and decreasekey can be realized in all, searching the element with the smallest priority requires a linear search.

Better you go here with the use of the data structure Fibonacci heap. This also enables the operations insert, empty and decreasekey ( amortized considered ) to realize the complexity of extractMin is here. The total run time is then only.

Applications

Directions are a prominent example in which this algorithm can be used. Here the graph represents the road network, which connects different points with each other. Wanted is the shortest route between two points.

Some topological indices, such as the J- index of Balaban, need weighted distances between the atoms of a molecule. The weighting is the bond order in such cases.

Dijkstra's algorithm is also used in the Internet as routing algorithm in OSPF and OLSR protocol. The latter Optimized Link State Routing protocol is adapted to the requirements of a mobile wireless LAN version of Link State routing. It is important for mobile ad hoc networks. One possible application of these are the outdoor wireless networks.

Other methods for the calculation of shortest paths

If one has enough information about the edge weights in the graph in order to derive a heuristic for the cost of individual nodes from them, it is possible to extend the algorithm of Dijkstra for the A * algorithm. To calculate all shortest paths from one node to all other nodes in a graph, one can also use the Bellman-Ford algorithm, which can deal with the negative edge weights. The algorithm of Floyd and Warshall finally calculates the shortest paths to each other all the nodes.

Algorithms for finding minimum spanning trees

• Algorithm of Kruskal
• Algorithm of Borůvka
• Algorithm of Prim