1  function Dijkstra(Graph, source):
2     for each vertex v in Graph:           // Initializations
3         dist[v] := infinity               // Unknown distance function from s to v
4         previous[v] := undefined
5     dist[source] := 0                     // Distance from s to s
6     Q := copy(Graph)                      // All nodes in the graph are unoptimized - 
                                            // thus are in Q
7     while Q is not empty:                 // The main loop
8         u := extract_min(Q)               // Remove best vertex from priority queue;
                                            // returns source on first iteration
9         for each neighbor v of u:         // where v has not yet been considered
10             alt = dist[u] + length(u, v)
11             if alt < dist[v]              // Relax (u,v)
12                 dist[v] := alt
13                 previous[v] := u
14     return previous[]