34 lines
853 B
Plaintext
34 lines
853 B
Plaintext
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)
|