50 lines
1.3 KiB
Plaintext
50 lines
1.3 KiB
Plaintext
include xpllib; \for Print
|
|
|
|
proc FloydWarshall(Weights, Len, Verts);
|
|
int Weights, Len, Verts;
|
|
int Dist, Next, I, J, K, W;
|
|
|
|
proc PrintResult;
|
|
int U, V;
|
|
[Print("Pair Dist Path\n");
|
|
for I:= 0 to Verts-1 do
|
|
for J:= 0 to Verts-1 do
|
|
if I # J then
|
|
[U:= I+1; V:= J+1;
|
|
Print("%d -> %d %2d %d", U, V, Dist(I,J), U);
|
|
repeat U:= Next(U-1, V-1);
|
|
Print(" -> %d", U);
|
|
until U = V;
|
|
Print("\n");
|
|
];
|
|
];
|
|
|
|
[Dist:= Reserve(Verts*IntSize);
|
|
for I:= 0 to Verts-1 do
|
|
[Dist(I):= Reserve(Verts*IntSize);
|
|
for J:= 0 to Verts-1 do
|
|
Dist(I,J):= \Inf\10000;
|
|
];
|
|
for W:= 0 to Len-1 do
|
|
Dist(Weights(W,0)-1, Weights(W,1)-1):= Weights(W,2);
|
|
Next:= Reserve(Verts*IntSize);
|
|
for I:= 0 to Verts-1 do
|
|
[Next(I):= Reserve(Verts*IntSize);
|
|
for J:= 0 to Verts-1 do
|
|
Next(I,J):= if I=J then 0 else J+1;
|
|
];
|
|
for K:= 0 to Verts-1 do
|
|
for I:= 0 to Verts-1 do
|
|
for J:= 0 to Verts-1 do
|
|
if Dist(I,J) > Dist(I,K) + Dist(K,J) then
|
|
[Dist(I,J):= Dist(I,K) + Dist(K,J);
|
|
Next(I,J):= Next(I,K);
|
|
];
|
|
PrintResult;
|
|
];
|
|
|
|
int Weights;
|
|
[Weights:= [ [1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1] ];
|
|
FloydWarshall(Weights, 5, 4);
|
|
]
|