contains pointers to previous-hop nodes on the shortest path from source to the given vertex (equivalently, it is the next-hop on the path from the given vertex to the source). The code , searches for the vertex in the vertex set that has the least value. returns the length of the edge joining (i.e. the distance between) the two neighbor-nodes and . The variable on line 14 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. 1 function Dijkstra(Graph, source): 2 3 for each vertex v in Graph.Vertices: 4 dist[v] ← INFINITY 5 prev[v] ← UNDEFINED 6 add v to Q 7 dist[source] ← 0 8 9 while Q is not empty: 10 u ← vertex in Q with min dist[u] 11 remove u from Q 12 13 for each neighbor v of u still in Q: 14 alt ← dist[u] + Graph.Edges(u, v) 15 if alt < dist[v]: 16 dist[v] ← alt 17 prev[v] ← u 18 19 return dist[], prev[] If we are only interested in a shortest path between vertices and , we can terminate the search after line 10 if . Now we can read the shortest path from to by reverse iteration: 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 constituting one of the shortest paths from to , or the empty sequence if no path exists. A more general problem would be to find all the shortest paths between and (there might be several different ones of the same length). Then instead of storing only a single node in each entry of we would store all nodes satisfying the relaxation condition. For example, if both and connect to and both of them lie on different shortest paths through (because the edge cost is the same in both cases), then we would add both and to .