(phixonline)-->
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)