24 lines
796 B
Text
24 lines
796 B
Text
|
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)])
|