dist[][]  // array of cost of shortest path from s to t
path[][]  // array of next node after s on shortest path from s to t

floydAPSP(G):
|  Input graph G
|
|  initialise dist[s][t]=0 for each s=t
|                       =w for each (s,t,w)∈edges(G)
|                       =∞ otherwise
|  initialise path[s][t]=t for each (s,t,w)∈edges(G)
|                       =-1 otherwise
|  for all i∈vertices(G) do
|  |  for all s∈vertices(G) do
|  |  |  for all t∈vertices(G) do
|  |  |  |  if dist[s][i]+dist[i][t] < dist[s][t] then
|  |  |  |     dist[s][t]=dist[s][i]+dist[i][t]
|  |  |  |     path[s][t]=path[s][i]
|  |  |  |  end if
|  |  |  end for
|  |  end for
|  end for