Floyd-Warshall algorithm

``````func floyd_warshall(n, edge) {
var dist = n.of {|i| n.of { |j| i == j ? 0 : Inf }}
var nxt  = n.of { n.of(nil) }
for u,v,w in edge {
dist[u-1][v-1] = w
nxt[u-1][v-1] = v-1
}

[^n] * 3 -> cartesian { |k, i, j|
if (dist[i][j] > dist[i][k]+dist[k][j]) {
dist[i][j] = dist[i][k]+dist[k][j]
nxt[i][j] = nxt[i][k]
}
}

var summary = "pair     dist    path\n"
for i,j (^n ~X ^n) {
i==j && next
var u = i
var path = [u]
while (u != j) {
path << (u = nxt[u][j])
}
path.map!{|u| u+1 }.join!(" -> ")
summary += ("%d -> %d  %4d     %s\n" % (i+1, j+1, dist[i][j], path))
}

return summary
}

var n = 4
var edge = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]
print floyd_warshall(n, edge)
``````

Output:

``````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
``````