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 + length(u, v)
11              if alt < dist[v]              // Relax (u,v)
12                  dist[v] := alt
13                  previous[v] := u
14      return previous[]