12345678910111213141516171819202122232425262728293031323334353637383940 |
- #!/usr/bin/ruby
- #
- ## https://rosettacode.org/wiki/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)
|