Dijkstra's algorithm

Dijkstra's algorithm is a method to find the shortest path from one node, or location, in a graph to all other nodes. In this process, it can find the shortest path from one node to another specific node. This can be used for navigation between points of interest like cities connected by roads, or finding the shortest chain of mutual friends from two people on a social media platform.

 Requirements and Limitations 
Dijkstra's algorithm works on a graph that has nodes and edges between those nodes. While the edges can have weight, representing a distance or cost, the algorithm also works on unweighted graphs by treating all edges as having a weight of 1.

The algorithm does not always find the shortest path on graphs with negative edge weights. Since the shortest path to a node is only determined once, potentially shorter paths from further away nodes with negative edge weights are not considered. 

The algorithm also does not try to visit nodes that are closer to the destination node. It visits nodes in order of total distance from the starting point, similar to Breadth-first search. This leads to many more nodes than needed being potentially visited to find the shortest path. 

 Algorithm  
The algorithm requires a starting node to be provided, a queue to track new nodes, and a table that saves the total distance required to reach each node. The queue starts with only the starting node in it associated with a total distance of 0. 

Until the destination node is reached, the algorithm repeats these steps:
 Take the node v with the shortest total distance out of the queue.
 Add all neighbors without a distance in the table to the queue with their distance from v.
 For each neighbor w, check the associated distance d of w. If d is greater than the distance from v to w :
 Update d in the queue to be the distance from v to w.
 Update w in the table to be this new distance. 
After the algorithm completes, the total distance from the start to end node can be found in the distance table.

A specific path from the start to the destination node can be found by repeating the following steps until the start node is reached, beginning with v being the end node:

 Start with d being infinity
 Check all neighbors w of v :
 If the total distance of w plus the distance from w to v is less than d, update d to that distance and set v to w.
 Continue checking the rest of the neighbors of the original v.
 Add the current v to the shortest path from the start to end node.

 Running time 
The number of steps that Dijkstra's algorithm needs to complete on any graph is based on the number of nodes V and the number of edges E between those nodes. In the implementation of Dijkstra's algorithm using a queue, the worst-case number of steps required is  (in Big O notation), or the number of edges |E| plus the number of nodes squared |V|2 as:

 |E| : all edges must be considered as potentially being the shortest path from one node to another. 
 |V|2 : all nodes must check the distance between them and all of their neighbors when being evaluated. In the worst-case scenario, all nodes could be connected to all other nodes.

 Related problems and algorithms 
Bellman-Ford is a shortest path algorithm that allows edges to have negative weights, but requires more steps to run.

A* is a shortest path algorithm that can try to visit nodes going towards the end node first. This algorithm requires knowing the positions of the nodes instead of just their distances to each other, as well as computing a "priority" value for each neighbor in each step. 

Pseudocode

In the pseudocode version of this algorithm's implementation, the code , searches for the vertex  in the vertex set  that has the least  value.  returns the length of the edge connecting the two neighbor-nodes  and . The variable  on line 18 is the length of the path from the root node to the neighbor node  if it were to go through . If this path is shorter than the current shortest path recorded for , that current path is replaced with this  path. The  array contains a pointer to the next node on the source graph to get the shortest route to the source.

  1  function Dijkstra(Graph, source):
  2
  3      create vertex set Q
  4
  5      for each vertex v in Graph:            
  6          dist[v] ← INFINITY                 
  7          prev[v] ← UNDEFINED                
  8          add v to Q                     
  9      dist[source] ← 0                       
 10     
 11      while Q is not empty:
 12          u ← vertex in Q with min dist[u]   
 13                                             
 14          remove u from Q
 15         
 16          for each neighbor v of u:           // only v that are still in Q
 17              alt ← dist[u] + length(u, v)
 18              if alt < dist[v]:              
 19                  dist[v] ← alt
 20                  prev[v] ← u
 21
 22      return dist[], prev[]

If we only want the shortest path between vertices  and , we can stop the search after line 15 if  (if the current node  is the target node).
Now we can read the shortest path from  to  by going backwards:

 1  S ← empty sequence
 2  u ← target
 3  if prev[u] is defined or u = source:          // Do something only if the vertex is reachable
 4      while u is defined:                       // Construct the shortest path with a stack S
 5          insert u at the beginning of S        // Push the vertex onto the stack
 6          u ← prev[u]                           // Traverse from target to source

Now sequence  is the list of vertices that make up one of the shortest paths from  to . If a path from  to  does not exist, sequence  will be empty.

References

Category:Algorithms
Category:Graph theory