58 lines
1.5 KiB
Plaintext
58 lines
1.5 KiB
Plaintext
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);
|