Floyd-Warshall algorithm: Difference between revisions
Added 11l
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 27:
* [https://www.youtube.com/watch?v=8WSZQwNtXPU Floyd-Warshall Algorithm - step by step guide (youtube)]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<lang 11l>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)])</lang>
{{out}}
<pre>
pair dist path
1 -> 2 -1 1 -> 3 -> 4 -> 2
1 -> 3 -2 1 -> 3
1 -> 4 0 1 -> 3 -> 4
2 -> 1 4 2 -> 1
2 -> 3 2 2 -> 1 -> 3
2 -> 4 4 2 -> 1 -> 3 -> 4
3 -> 1 5 3 -> 4 -> 2 -> 1
3 -> 2 1 3 -> 4 -> 2
3 -> 4 2 3 -> 4
4 -> 1 3 4 -> 2 -> 1
4 -> 2 -1 4 -> 2
4 -> 3 1 4 -> 2 -> 1 -> 3
</pre>
=={{header|360 Assembly}}==
{{trans|Rexx}}
| |||