Floyd-Warshall algorithm: Difference between revisions
Content added Content deleted
(→{{header|Kotlin}}: Updated example see https://github.com/dkandalov/rosettacode-kotlin for details) |
(Adding SequenceL version) |
||
Line 985: | Line 985: | ||
4 -> 2 -1 4 -> 2 |
4 -> 2 -1 4 -> 2 |
||
4 -> 3 1 4 -> 2 -> 1 -> 3 |
4 -> 3 1 4 -> 2 -> 1 -> 3 |
||
</pre> |
|||
=={{header|SequenceL}}== |
|||
{{trans|GO}} |
|||
<lang sequencel>import <Utilities/Sequence.sl>; |
|||
import <Utilities/Math.sl>; |
|||
ARC ::= (To: int, Weight: float); |
|||
arc(t,w) := (To: t, Weight: w); |
|||
VERTEX ::= (Label: int, Arcs: ARC(1)); |
|||
vertex(l,arcs(1)) := (Label: l, Arcs: arcs); |
|||
getArcsFrom(vertex, graph(1)) := |
|||
let |
|||
index := firstIndexOf(graph.Label, vertex); |
|||
in |
|||
[] when index = 0 |
|||
else |
|||
graph[index].Arcs; |
|||
getWeightTo(vertex, arcs(1)) := |
|||
let |
|||
index := firstIndexOf(arcs.To, vertex); |
|||
in |
|||
0 when index = 0 |
|||
else |
|||
arcs[index].Weight; |
|||
throughK(k, dist(2)) := |
|||
let |
|||
newDist[i, j] := min(dist[i][k] + dist[k][j], dist[i][j]); |
|||
in |
|||
dist when k > size(dist) |
|||
else |
|||
throughK(k + 1, newDist); |
|||
floydWarshall(graph(1)) := |
|||
let |
|||
initialResult[i,j] := 1.79769e308 when i /= j else 0 |
|||
foreach i within 1 ... size(graph), |
|||
j within 1 ... size(graph); |
|||
singleResult[i,j] := getWeightTo(j, getArcsFrom(i, graph)) |
|||
foreach i within 1 ... size(graph), |
|||
j within 1 ... size(graph); |
|||
start[i,j] := |
|||
initialResult[i,j] when singleResult[i,j] = 0 |
|||
else |
|||
singleResult[i,j]; |
|||
in |
|||
throughK(1, start); |
|||
main() := |
|||
let |
|||
graph := [vertex(1, [arc(3,-2)]), |
|||
vertex(2, [arc(1,4), arc(3,3)]), |
|||
vertex(3, [arc(4,2)]), |
|||
vertex(4, [arc(2,-1)])]; |
|||
in |
|||
floydWarshall(graph);</lang> |
|||
{{out}} |
|||
<pre> |
|||
[[0,-1,-2,0],[4,0,2,4],[5,1,0,2],[3,-1,1,0]] |
|||
</pre> |
</pre> |
||