Anonymous user
Floyd-Warshall algorithm: Difference between revisions
Adding SequenceL version
(→{{header|Kotlin}}: Updated example see https://github.com/dkandalov/rosettacode-kotlin for details) |
(Adding SequenceL version) |
||
Line 985:
4 -> 2 -1 4 -> 2
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>
| |||