Floyd-Warshall algorithm: Difference between revisions
m (→{{header|J}}) |
m (→{{header|J}}) |
||
Line 5: | Line 5: | ||
=={{header|J}}== |
=={{header|J}}== |
||
<lang J>(<. <./ .+/~)^:_</lang> |
<lang J>(<. <./ .+/~)^:_</lang> |
||
Example use: |
Example use: |
||
Line 17: | Line 17: | ||
_ _ _ _ _ 9 |
_ _ _ _ _ 9 |
||
_ _ _ _ _ _ |
_ _ _ _ _ _ |
||
(<. <./ .+/~)^:_ graph |
(<. <./ .+/~)^:_ graph |
||
_ 7 9 20 _3 2 |
_ 7 9 20 _3 2 |
||
_ _ 10 15 21 _5 |
_ _ 10 15 21 _5 |
Revision as of 08:05, 10 October 2015
The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights.
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>