Dijkstra's algorithm

Dijkstra's algorithm is a method to find the shortest paths between nodes in a graph. It is faster than many other ways to do this, but it needs all of the distances between nodes in the graph to be zero or more.
Algorithm.
When you have done all of these steps you can use the list to find the shortest way from the first thing to any other thing. First write down the other thing. Then keep doing these steps:
The connections between the things you have written down are the shortest way from the first thing to the other thing.
Pseudocode.
In this pseudocode algorithm, 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" &lt; 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.