# Artificial Intelligence/Search/Dijkstra's Algorithm

## OverviewEdit

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 AlgorithmEdit

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.

## PseudocodeEdit

*(this section taken directly from wikipedia)*
In the following algorithm, the code `u := node in `

, searches for the vertex *Q* with smallest dist[]`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.

1functionDijkstra(Graph,source): 2for eachvertexvinGraph:// Initializations3 dist[v] := infinity// Unknown distance function from source to v4 previous[v] := undefined// Previous node in optimal path from source5 dist[source] := 0// Distance from source to source6Q:= the set of all nodes inGraph// All nodes in the graph are unoptimized - thus are in Q7whileQis notempty:// The main loop8u:= vertex inQwith smallest dist[] 9ifdist[u] = infinity: 10break// all remaining vertices are inaccessible11 removeufromQ12for eachneighborvofu:// where v has not yet been removed from Q.13alt:= dist[u] + dist_between(u,v) 14ifalt< dist[v]:// Relax (u,v,a)15 dist[v] :=alt16 previous[v] :=u17returnprevious[]

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:

1S:= empty sequence 2u:=target3whileprevious[u] is defined: 4 insertuat the beginning ofS5u:= 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.

## ReferencesEdit

- 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 linksEdit

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