Floyd-Warshall algorithm: Difference between revisions
Content added Content deleted
m (→{{header|ALGOL 68}}: fix bugette) |
(Show the output required by the task, use the task sample data instead of random data) |
||
Line 3,174: | Line 3,174: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
Using output code translated from the Lua sample. |
|||
{{output?|Javascript}} |
|||
<syntaxhighlight lang="javascript"> |
<syntaxhighlight lang="javascript">'use strict' |
||
let numVertices = 4; |
|||
⚫ | |||
let weights = [ [ 1, 3, -2 ], [ 2, 1, 4 ], [ 2, 3, 3 ], [ 3, 4, 2 ], [ 4, 2, -1 ] ]; |
|||
let graph = []; |
|||
⚫ | |||
graph.push([]); |
graph.push([]); |
||
for (j = 0; j < |
for (let j = 0; j < numVertices; ++j) |
||
graph[i].push(i == j ? 0 : 9999999); |
graph[i].push(i == j ? 0 : 9999999); |
||
} |
} |
||
for (i = |
for (let i = 0; i < weights.length; ++i) { |
||
let w = weights[i]; |
|||
graph[0][i] = graph[i][0] = parseInt(Math.random() * 9 + 1); |
|||
graph[w[0] - 1][w[1] - 1] = w[2]; |
|||
} |
|||
let nxt = []; |
|||
⚫ | |||
nxt.push([]); |
|||
for (let j = 0; j < numVertices; ++j) |
|||
nxt[i].push(i == j ? 0 : j + 1); |
|||
} |
|||
for (let k = 0; k < numVertices; ++k) { |
|||
for (let i = 0; i < numVertices; ++i) { |
|||
for (let j = 0; j < numVertices; ++j) { |
|||
if (graph[i][j] > graph[i][k] + graph[k][j]) { |
|||
graph[i][j] = graph[i][k] + graph[k][j]; |
|||
nxt[i][j] = nxt[i][k]; |
|||
} |
|||
} |
|||
} |
|||
} |
} |
||
console.log("pair dist path"); |
|||
⚫ | |||
for (let i = 0; i < numVertices; ++i) { |
|||
for (let j = 0; j < numVertices; ++j) { |
|||
if (i != j) { |
|||
let u = i + 1; |
|||
let v = j + 1; |
|||
let path = u + " -> " + v + " " + graph[i][j].toString().padStart(2) + " " + u; |
|||
do { |
|||
u = nxt[u - 1][v - 1]; |
|||
path = path + " -> " + u; |
|||
} while (u != v); |
|||
console.log(path) |
|||
} |
} |
||
} |
} |
||
} |
} |
||
⚫ | |||
{{out}} |
|||
⚫ | |||
<pre> |
|||
pair dist path |
|||
1 -> 2 -1 1 -> 3 -> 4 -> 2 |
|||
1 -> 3 -2 1 -> 3 |
|||
1 -> 4 0 1 -> 3 -> 4 |
|||
2 -> 1 4 2 -> 1 |
|||
2 -> 3 2 2 -> 1 -> 3 |
|||
2 -> 4 4 2 -> 1 -> 3 -> 4 |
|||
3 -> 1 5 3 -> 4 -> 2 -> 1 |
|||
3 -> 2 1 3 -> 4 -> 2 |
|||
3 -> 4 2 3 -> 4 |
|||
4 -> 1 3 4 -> 2 -> 1 |
|||
4 -> 2 -1 4 -> 2 |
|||
4 -> 3 1 4 -> 2 -> 1 -> 3 |
|||
</pre> |
|||
=={{header|jq}}== |
=={{header|jq}}== |