The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights.




Task
Find the lengths of the shortest paths between all pairs of vertices of the given directed graph. Your code may assume that the input has already been checked for loops, parallel edges and negative cycles.


Print the pair, the distance and (optionally) the path.




Example
pair     dist    path
1 -> 2    -1     1 -> 3 -> 4 -> 2
1 -> 3    -2     1 -> 3
1 -> 4     0     1 -> 3 -> 4
2 -> 1     4     2 -> 1
2 -> 3     2     2 -> 1 -> 3
2 -> 4     4     2 -> 1 -> 3 -> 4
3 -> 1     5     3 -> 4 -> 2 -> 1
3 -> 2     1     3 -> 4 -> 2
3 -> 4     2     3 -> 4
4 -> 1     3     4 -> 2 -> 1
4 -> 2    -1     4 -> 2
4 -> 3     1     4 -> 2 -> 1 -> 3


See also
 Floyd-Warshall Algorithm - step by step guide (youtube)


constant inf = 1e300*1e300
 
function Path(integer u, integer v, sequence next)
    if next[u,v]=null then
       return ""
    end if
    sequence path = {sprintf("%d",u)}
    while u!=v do
       u = next[u,v]
       path = append(path,sprintf("%d",u))
    end while
    return join(path,"->")
end function
 
procedure FloydWarshall(integer V, sequence weights)
    sequence dist = repeat(repeat(inf,V),V)
    sequence next = repeat(repeat(null,V),V)
    for k=1 to length(weights) do
      integer {u,v,w} = weights[k]
      dist[u,v] := w  -- the weight of the edge (u,v)
      next[u,v] := v
    end for
    -- standard Floyd-Warshall implementation
    for k=1 to V do
      for i=1 to V do
        for j=1 to V do
          atom d = dist[i,k] + dist[k,j]
          if dist[i,j] > d then
            dist[i,j] := d
            next[i,j] := next[i,k]
          end if
        end for
      end for
    end for
    printf(1,"pair  dist  path\n")
    for u=1 to V do
      for v=1 to V do
        if u!=v then
          printf(1,"%d->%d   %2d   %s\n",{u,v,dist[u,v],Path(u,v,next)})
        end if
      end for
    end for
end procedure   
 
constant V = 4
constant weights = {{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}}
FloydWarshall(V,weights)
