Artificial Intelligence/Search/Dijkstra's Algorithm

Overview

Dijkstra’s algorithm is used for graph searches. It is optimal, meaning it will find the single shortest path. It is uninformed, meaning it does not need to know the target node before hand. In fact it finds the shortest path from every node to the node of origin. There are many possible variations of Dijkstra’s algorithm optimized for specific purposes. One example is that if a destination node is known the algorithm can be instructed to terminate once it has found the shortest path for that node. Dijkstra's algorithm can be considered a heuristic search, similar to a greedy search if the search has a known destination and it can be considered an exhaustive search when the search has no destination node and all nodes are considered. The efficient of Dijkstra’s algorithm makes it a favorite for network routing protocols. Also since essentially any combinatorial optimization problem can be formulated as a shortest path problem, Dijkstra’s algorithm is also important for AI research.

Description of the Algorithm

Dijkstra’s algorithm needs a node of origin to begin at. It will find the shortest distance to all other nodes from that node of origin. For every node it needs memory to store a distance value and a flag that marks a node as visited or unvisited. It also needs a pointer to keep track of the current node.

Assign the node of origin a distance value of zero and all other nodes a distance value of infinity.
Mark all nodes as unvisited and set the node of origin as the current node.
For the current node consider all of its unvisited neighbors and calculate its distance from the node of origin using the path through the current node. If the calculated distance of the unvisited neighbor through the path containing the current node is less than its distance value overwrite the distance value using the new value.
When all the neighbors of the current node have been considered flag the current node as visited. A visited node will never be checked again its value is final and minimal.
Set the unvisited node with the lowest distance value as the current node and continue from step 3.

Pseudocode

(this section taken directly from wikipedia) In the following algorithm, the code u := node in Q with smallest dist[], searches for the vertex u in the vertex set Q that has the least dist[u] value. That vertex is removed from the set Q and returned to the user. dist_between(u, v) calculates the length between the two neighbor-nodes u and v. alt on line 11 is the length of the path from the root node to the neighbor node v if it were to go through u. If this path is shorter than the current shortest path recorded for v, that current path is replaced with this alt path. The previous array is populated with a pointer to the "next-hop" node on the source graph to get the shortest route to the source.

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from source to v
 4          previous[v] := undefined          // Previous node in optimal path from source
 5      dist[source] := 0                     // Distance from source to source
 6      Q := the set of all nodes in Graph
        // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop
 8          u := vertex in Q with smallest dist[]
 9          if dist[u] = infinity:
10              break                         // all remaining vertices are inaccessible
11          remove u from Q
12          for each neighbor v of u:         // where v has not yet been removed from Q.
13              alt := dist[u] + dist_between(u, v) 
14              if alt < dist[v]:             // Relax (u,v,a)
15                  dist[v] := alt
16                  previous[v] := u
17      return previous[]

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

1  S := empty sequence
2  u := target
3  while previous[u] is defined:
4      insert u at the beginning of S
5      u := previous[u]

Now sequence S is the list of vertices constituting one of the shortest paths from target to source, or the empty sequence if no path exists.

A more general problem would be to find all the shortest paths between source and target (there might be several different ones of the same length). Then instead of storing only a single node in each entry of previous[] we would store all nodes satisfying the relaxation condition. For example, if both r and source connect to target and both of them lie on different shortest paths through target (because the edge cost is the same in both cases), then we would add both r and source to previous[target]. When the algorithm completes, previous[] data structure will actually describe a graph that is a subset of the original graph with some edges removed. Its key property will be that if the algorithm was run with some starting node, then every path from that node to any other node in the new graph will be the shortest path between those nodes in the original graph, and all paths of that length from the original graph will be present in the new graph. Then to actually find all these short paths between two given nodes we would use a path finding algorithm on the new graph, such as depth-first search.

References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.3: Dijkstra's algorithm, pp.595–601.
Wikipedia (2009/03/11). http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Dijkstra's Algorithm revisited: the OR/MS Connexion (2009/04/11). http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/index.html

External links

Dijkstra's Shortest Path Algorithm Applet. http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html