Floyd-Warshall algorithm: Difference between revisions

</pre>

=={{header|Phix}}==

Direct translation of the wikipedia pseudocode

<lang Phix>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)</lang>

{{out}}

<pre>

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