Rosetta Code

Floyd-Warshall algorithm: Difference between revisions

Page Discussion

Floyd-Warshall algorithm (view source)

Revision as of 14:19, 25 May 2021

12,626 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 1,794:
=={{header|Phix}}==
Direct translation of the wikipedia pseudocode
<!--<lang Phix>constant inf = 1e300*1e300(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;">"-&gt;"</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>
<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-&gt;%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}}
<pre>
Petelomax
7,805

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/261971"