Floyd-Warshall algorithm: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
Line 1,794: | Line 1,794: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Direct translation of the wikipedia pseudocode |
Direct translation of the wikipedia pseudocode |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">constant</span> <span style="color: #000000;">inf</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e300</span><span style="color: #0000FF;">*</span><span style="color: #000000;">1e300</span> |
|||
function Path(integer u, integer v, sequence next) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">Path</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">)</span> |
|||
if next[u,v]=null then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">]=</span><span style="color: #004600;">null</span> <span style="color: #008080;">then</span> |
|||
return "" |
|||
<span style="color: #008080;">return</span> <span style="color: #008000;">""</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
sequence path = {sprintf("%d",u)} |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">path</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">u</span><span style="color: #0000FF;">)}</span> |
|||
while u!=v do |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">v</span> <span style="color: #008080;">do</span> |
|||
u = next[u,v] |
|||
<span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">]</span> |
|||
path = append(path,sprintf("%d",u)) |
|||
<span style="color: #000000;">path</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">u</span><span style="color: #0000FF;">))</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
return join(path,"->") |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"->"</span><span style="color: #0000FF;">)</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
procedure FloydWarshall(integer V, sequence weights) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">FloydWarshall</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">V</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">weights</span><span style="color: #0000FF;">)</span> |
|||
sequence dist = repeat(repeat(inf,V),V) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dist</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">V</span><span style="color: #0000FF;">),</span><span style="color: #000000;">V</span><span style="color: #0000FF;">)</span> |
|||
sequence next = repeat(repeat(null,V),V) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">null</span><span style="color: #0000FF;">,</span><span style="color: #000000;">V</span><span style="color: #0000FF;">),</span><span style="color: #000000;">V</span><span style="color: #0000FF;">)</span> |
|||
for k=1 to length(weights) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">weights</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
integer {u,v,w} = weights[k] |
|||
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">weights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> |
|||
dist[u,v] := w -- the weight of the edge (u,v) |
|||
<span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">w</span> <span style="color: #000080;font-style:italic;">-- the weight of the edge (u,v)</span> |
|||
next[u,v] := v |
|||
<span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">v</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
-- standard Floyd-Warshall implementation |
<span style="color: #000080;font-style:italic;">-- standard Floyd-Warshall implementation</span> |
||
for k=1 to V do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">V</span> <span style="color: #008080;">do</span> |
|||
for i=1 to V do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">V</span> <span style="color: #008080;">do</span> |
|||
for j=1 to V do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">V</span> <span style="color: #008080;">do</span> |
|||
atom d = dist[i,k] + dist[k,j] |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
if dist[i,j] > d then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">d</span> <span style="color: #008080;">then</span> |
|||
dist[i,j] := d |
|||
<span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">d</span> |
|||
next[i,j] := next[i,k] |
|||
<span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
printf(1,"pair dist path\n") |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"pair dist path\n"</span><span style="color: #0000FF;">)</span> |
|||
for u=1 to V do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">V</span> <span style="color: #008080;">do</span> |
|||
for v=1 to V do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">V</span> <span style="color: #008080;">do</span> |
|||
if u!=v then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">v</span> <span style="color: #008080;">then</span> |
|||
printf(1,"%d->%d %2d %s\n",{u,v,dist[u,v],Path(u,v,next)}) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d->%d %2d %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">],</span><span style="color: #000000;">Path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)})</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
constant V = 4 |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">V</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span> |
|||
constant weights = {{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}} |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">weights</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span> |
|||
FloydWarshall(V,weights)</lang> |
|||
<span style="color: #000000;">FloydWarshall</span><span style="color: #0000FF;">(</span><span style="color: #000000;">V</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weights</span><span style="color: #0000FF;">)</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |