Floyd-Warshall algorithm
The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights.
EchoLisp
Transcription of the Floyd-Warshall algorithm, with best path computation. <lang scheme> (lib 'matrix)
- in
- initialized dist and next matrices
- out
- dist and next matrices
- O(n^3)
(define (floyd-with-path n dist next (d 0))
(for* ((k n) (i n) (j n))
#:break (< (array-ref dist j j) 0) => 'negative-cycle
(set! d (+ (array-ref dist i k) (array-ref dist k j)))
(when (< d (array-ref dist i j)) (array-set! dist i j d) (array-set! next i j (array-ref next i k)))))
- utilities
- init random edges costs, matrix 66% filled
(define (init-edges n dist next)
(for* ((i n) (j n))
(array-set! dist i i 0)
(array-set! next i j null) #:continue (= j i) (array-set! dist i j Infinity)
#:continue (< (random) 0.3) (array-set! dist i j (1+ (random 100)))
(array-set! next i j j)))
- show path from u to v
(define (path u v) (cond ((= u v) (list u)) ((null? (array-ref next u v)) null)
(else (cons u (path (array-ref next u v) v)))))
(define( mdist u v) ;; show computed distance (array-ref dist u v))
(define (task) (init-edges n dist next) (array-print dist) ;; show init distances (floyd-with-path n dist next))
</lang>
- Output:
(task) 0 Infinity Infinity 13 98 Infinity 35 47 8 0 Infinity Infinity 83 77 16 3 73 3 0 3 76 84 91 Infinity 30 49 Infinity 0 41 Infinity 4 4 22 83 92 Infinity 0 30 27 98 6 Infinity Infinity 24 59 0 Infinity Infinity 60 Infinity 45 Infinity 67 100 0 Infinity 72 15 95 21 Infinity Infinity 27 0 (array-print dist) ;; computed distances 0 32 62 13 54 84 17 17 8 0 61 21 62 77 16 3 11 3 0 3 44 74 7 6 27 19 49 0 41 71 4 4 22 54 72 35 0 30 27 39 6 38 68 19 59 0 23 23 56 48 45 48 67 97 0 51 23 15 70 21 62 92 25 0 (path 1 3) → (1 0 3) (mdist 1 0) → 8 (mdist 0 3) → 13 (mdist 1 3) → 21 ;; = 8 + 13 (path 7 6) → (7 3 6) (path 6 7) → (6 2 1 7)
J
<lang J>(<. <./ .+/~)^:_</lang>
Example use:
<lang J> graph=: (_#&.>~1+i.6),&>6{.(#~5 4 3 2 1) </. 7 9 _ _3 14 10 15 _ _5 11 _ 2 6 _ 9
graph
_ 7 9 _ _3 14 _ _ 10 15 _ _5 _ _ _ 11 _ 2 _ _ _ _ 6 _ _ _ _ _ _ 9 _ _ _ _ _ _
(<. <./ .+/~)^:_ graph
_ 7 9 20 _3 2 _ _ 10 15 21 _5 _ _ _ 11 17 2 _ _ _ _ 6 15 _ _ _ _ _ 9 _ _ _ _ _ _</lang>
The graph matrix holds the costs of each directed node. Row index is index of starting node. Column index is index of ending node. Unconnected nodes have infinite cost.
JavaScript
<lang javascript>var graph = []; for (i = 0; i < 10; ++i) {
graph.push([]); for (j = 0; j < 10; ++j) graph[i].push(i == j ? 0 : 9999999);
}
for (i = 1; i < 10; ++i) {
graph[0][i] = graph[i][0] = parseInt(Math.random() * 9 + 1);
}
for (k = 0; k < 10; ++k) {
for (i = 0; i < 10; ++i) { for (j = 0; j < 10; ++j) { if (graph[i][j] > graph[i][k] + graph[k][j]) graph[i][j] = graph[i][k] + graph[k][j] } }
}
console.log(graph);</lang>
PHP
<lang php><?php $graph = array(); for ($i = 0; $i < 10; ++$i) {
$graph[] = array(); for ($j = 0; $j < 10; ++$j) $graph[$i][] = $i == $j ? 0 : 9999999;
}
for ($i = 1; $i < 10; ++$i) {
$graph[0][$i] = $graph[$i][0] = rand(1, 9);
}
for ($k = 0; $k < 10; ++$k) {
for ($i = 0; $i < 10; ++$i) { for ($j = 0; $j < 10; ++$j) { if ($graph[$i][$j] > $graph[$i][$k] + $graph[$k][$j]) $graph[$i][$j] = $graph[$i][$k] + $graph[$k][$j]; } }
}
print_r($graph); ?></lang>
Ruby
<lang ruby>require 'matrix'
graph = [] 10.times{|i| graph[i] = [].fill(9999999, 0, 10)} 10.times{|i| graph[i][i] = 0} (1..9).each{|i| graph[i][0] = graph[0][i] = Random.rand(9) + 1}
10.times do |k|
10.times do |i| 10.times do |j| graph[i][j] = graph[i][k] + graph[k][j] if graph[i][j] > graph[i][k] + graph[k][j] end end
end
puts Matrix[graph]</lang>