Floyd-Warshall algorithm: Difference between revisions
Content added Content deleted
(Creating the page with three languages : javascript, ruby and PHP) |
No edit summary |
||
Line 1: | Line 1: | ||
{{task}} |
{{draft task}} |
||
The [[wp:Floyd–Warshall_algorithm|Floyd–Warshall algorithm]] is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. |
The [[wp:Floyd–Warshall_algorithm|Floyd–Warshall algorithm]] is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. |
||
Revision as of 05:09, 10 October 2015
Floyd-Warshall algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights.
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>