# distance(j) is distance from source vertex to vertex j
# parent(j) is the vertex that precedes vertex j in any shortest path
# (to reconstruct the path subsequently)
1 For all nodes i
2 distance(i) = infinity # not reachable yet
3 visited(i) = False
4 parent(i) = nil # no path to vertex yet
5 distance(source) = 0 # source -> source is start of all paths
6 parent(source) = nil
7 8 while (nodesvisited < graphsize)
9 find unvisited vertex with min distance to source; call it vertex i
10 assert (distance(i) != infinity, "Graph is not connected")
11 visited(i) = True # mark vertex i as visited
# update distances of neighbors of i
12 For all neighbors j of vertex i
13 if distance(i) + weight(i,j) < distance(j) then
14 distance(j) = distance(i) + weight(i,j)
15 parent(j) = i
# dist(i,j) is "best" distance so far from vertex i to vertex j
# Start with all single edge paths.
For i = 1 to n do
For j = 1 to n do
dist(i,j) = weight(i,j)
For k = 1 to n do # k is the `intermediate' vertex
For i = 1 to n do
For j = 1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j)) then # shorter path?
dist(i,j) = dist(i,k) + dist(k,j)