Dijkstra's algorithm

From Wikipedia, the free encyclopedia - View original article

Dijkstra's algorithm
Dijkstra's algorithm runtime
Dijkstra's algorithm. It picks the unvisited vertex with the lowest-distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.
ClassSearch algorithm
Data structureGraph
Worst case performanceO(|E| + |V| \log|V|)
Jump to: navigation, search
Not to be confused with Dykstra's projection algorithm.
Dijkstra's algorithm
Dijkstra's algorithm runtime
ClassSearch algorithm
Data structureGraph

Dijkstra's algorithm, conceived by computer scientist Edsger Dijkstra in 1956 and published in 1959,[1][2] is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.


Dijkstra's original algorithm does not use a min-priority queue and runs in time O(|V|^2) (where |V| is the number of vertices). The idea of this algorithm is also given in (Leyzorek et al. 1957). The implementation based on a min-priority queue implemented by a Fibonacci heap and running in O(|E|+|V|\log|V|) (where |E| is the number of edges) is due to (Fredman & Tarjan 1984). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.


Illustration of Dijkstra's algorithm search for finding path from a start node (lower left, red) to a goal node (upper right, green) in a robot motion planning problem. Open nodes represent the "tentative" set. Filled nodes are visited ones, with color representing the distance: the greener, the farther. Nodes in all the different directions are explored uniformly, appearing as a more-or-less circular wavefront as Dijkstra's algorithm uses a heuristic identically equal to 0.


  6. Select the unvisited node that is marked with the smallest tentative distance, and set it as the new "current node" then go back to step 3.


Note: For ease of understanding, this discussion uses the terms intersection, road and map — however, in formal notation these terms are vertex, edge and graph, respectively.

Suppose you would like to find the shortest path between two intersections on a city map, a starting point and a destination. The order is conceptually simple: to start, mark the distance to every intersection on the map with infinity. This is done not to imply there is an infinite distance, but to note that intersection has not yet been visited; some variants of this method simply leave the intersection unlabeled. Now, at each iteration, select a current intersection. For the first iteration, the current intersection will be the starting point and the distance to it (the intersection's label) will be zero. For subsequent iterations (after the first), the current intersection will be the closest unvisited intersection to the starting point—this will be easy to find.



Of note is the fact that this algorithm makes no attempt to direct "exploration" towards the destination as one might expect. Rather, the sole consideration in determining the next "current" intersection is its distance from the starting point. This algorithm, therefore "expands outward" from the starting point, interactively considering every node that is closer in terms of shortest path distance until it reaches the destination. When understood in this way, it is clear how the algorithm necessarily finds the shortest path, however, it may also reveal one of the algorithm's weaknesses: its relative slowness in some topologies.



  1  function Dijkstra(Graph, source):  2      dist[source]  := 0                     // Distance from source to source  3      for each vertex v in Graph:            // Initializations  4          if vsource  5              dist[v]  := infinity           // Unknown distance function from source to v  6              previous[v]  := undefined      // Previous node in optimal path from source  7          end if   8          add v to Q                         // All nodes initially in Q  9      end for 10       11      while Q is not empty:                  // The main loop 12          u := vertex in Q with min dist[u]  // Source node in first case 13          remove u from Q  14           15          for each neighbor v of u:           // where v has not yet been removed from Q. 16              alt := dist[u] + length(u, v) 17              if alt < dist[v]:               // A shorter path to v has been found 18                  dist[v]  := alt  19                  previous[v]  := u  20              end if 21          end for 22      end while 23      return dist[], previous[] 24  end function 

If we are only interested in a shortest path between vertices source and target, we can terminate the search at line 13 if u = target. Now we can read the shortest path from source to target by reverse iteration:

 1  S := empty sequence 2  u := target 3  while previous[u] is defined:                // Construct the shortest path with a stack S 4      insert u at the beginning of S           // Push the vertex into the stack 5      u := previous[u]                         // Traverse from target to source 6  end while 



Using a priority queue[edit]


 1  function Dijkstra(Graph, source): 2      dist[source] := 0                     // Initializations 3      for each vertex v in Graph:            4          if vsource 5              dist[v] := infinity           // Unknown distance from source to v 6              previous[v] := undefined      // Predecessor of v 7          end if 8          PQ.add_with_priority(v,dist[v]) 9      end for  10 11 12     while PQ is not empty:                // The main loop 13         u := PQ.extract_min()             // Remove and return best vertex 14         for each neighbor v of u:         // where v has not yet been removed from PQ. 15             alt = dist[u] + length(u, v)  16             if alt < dist[v]               17                 dist[v] := alt  18                 previous[v] := u 19                 PQ.decrease_priority(v,alt) 20             end if 21         end for 22     end while 23     return previous[] 

It should be noted that other data structures can be used to achieve even faster computing times in practice.[3]

Running time[edit]

An upper bound of the running time of Dijkstra's algorithm on a graph with edges E and vertices V can be expressed as a function of |E| and |V| using big-O notation.

For any implementation of vertex set Q the running time is in O(|E| \cdot dk_Q + |V| \cdot em_Q), where dk_Q and em_Q are times needed to perform decrease key and extract minimum operations in set Q, respectively.

The simplest implementation of the Dijkstra's algorithm stores vertices of set Q in an ordinary linked list or array, and extract minimum from Q is simply a linear search through all vertices in Q. In this case, the running time is O(|E| + |V|^2) = O(|V|^2).

For sparse graphs, that is, graphs with far fewer than O(|V|^2) edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap as a priority queue to implement extracting minimum efficiently. With a self-balancing binary search tree or binary heap, the algorithm requires \Theta((|E| + |V|) \log |V|) time (which is dominated by \Theta( | E | \log | V | ), assuming the graph is connected). To avoid O(|V|) look-up in decrease-key step on a vanilla binary heap, it is necessary to maintain a supplementary index mapping each vertex to the heap's index (and keep it up to date as priority queue Q changes), making it take only O(\log|V|) time instead. The Fibonacci heap improves this to O(|E| + |V| \log|V|).


Related problems and algorithms[edit]








Dynamic programming perspective[edit]

From a dynamic programming point of view, Dijkstra's algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.[5][6][7]

In fact, Dijkstra's explanation of the logic behind the algorithm,[8] namely

Problem 2. Find the path of minimum total length between two given nodes P and Q.

We use the fact that, if R is a node on the minimal path from P to Q, knowledge of the latter implies the knowledge of the minimal path from P to R.


See also[edit]


  1. ^ Dijkstra, Edsger; Thomas J. Misa, Editor (August 2010). "An Interview with Edsger W. Dijkstra". Communications of the ACM 53 (8): 41–47. doi:10.1145/1787234.1787249. "What is the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path which I designed in about 20 minutes. One morning I was shopping with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path." 
  2. ^ Dijkstra 1959
  3. ^ Chen, M.; Chowdhury, R. A.; Ramachandran, V.; Roche, D. L.; Tong, L. (2007). Priority Queues and Dijkstra’s Algorithm — UTCS Technical Report TR-07-54 — 12 October 2007. Austin, Texas: The University of Texas at Austin, Department of Computer Sciences. 
  4. ^ http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dag_shortest_paths.html
  5. ^ Sniedovich, M. (2006). "Dijkstra’s algorithm revisited: the dynamic programming connexion" (PDF). Journal of Control and Cybernetics 35 (3): 599–620.  Online version of the paper with interactive computational modules.
  8. ^ Dijkstra 1959, p. 270


External links[edit]