Dijkstras Algorithm

Dijkstra's Algorithm

Dijkstra's Algorithm is a graph search algorithm to find the shortest path between a given node and all other nodes in a network. It is O(|V|), but an implementation has been described that is O(|E|+|V|log|V|). A generalization with potentially even lower time complexity is the A* algorithm, which can be applied if a heuristic estimate of the distance to the goal node can be defined.

 

Algorithm

Original source taken from Dijkstra's algorithm.

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          remove u from Q
10          for each neighbor v of u:         // where v has not yet been removed from Q.
11              alt := dist[u] + dist_between(u, v)       // be careful in 1st step - dist[u] is infinity yet
12              if alt < dist[v]              // Relax (u,v,a)
13                  dist[v] := alt
14                  previous[v] := u
15      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 defined previous[u]
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.

   

Further reading and resources