24 lines
796 B
Plaintext
24 lines
796 B
Plaintext
F floyd_warshall(n, edge)
|
||
V rn = 0 .< n
|
||
V dist = rn.map(i -> [1'000'000] * @n)
|
||
V nxt = rn.map(i -> [0] * @n)
|
||
L(i) rn
|
||
dist[i][i] = 0
|
||
L(u, v, w) edge
|
||
dist[u - 1][v - 1] = w
|
||
nxt[u - 1][v - 1] = v - 1
|
||
L(k, i, j) cart_product(rn, rn, rn)
|
||
V sum_ik_kj = dist[i][k] + dist[k][j]
|
||
I dist[i][j] > sum_ik_kj
|
||
dist[i][j] = sum_ik_kj
|
||
nxt[i][j] = nxt[i][k]
|
||
print(‘pair dist path’)
|
||
L(i, j) cart_product(rn, rn)
|
||
I i != j
|
||
V path = [i]
|
||
L path.last != j
|
||
path.append(nxt[path.last][j])
|
||
print(‘#. -> #. #4 #.’.format(i + 1, j + 1, dist[i][j], path.map(p -> String(p + 1)).join(‘ -> ’)))
|
||
|
||
floyd_warshall(4, [(1, 3, -2), (2, 1, 4), (2, 3, 3), (3, 4, 2), (4, 2, -1)])
|