Published by Dimitris Kougioumtzis · Updated
Allow each node as an intermediate stop and update every source/destination pair.
At phase k, allow vertex k as an intermediate for every source-target pair, progressively broadening possible routes.
When to use Floyd–Warshall all-pairs shortest paths
Many pairwise route queries on a small graph.
Choosing an alternative
Repeated Dijkstra can suit sparse nonnegative graphs.
Worked example: input and state changes
Example input
0,1,4; 0,2,2; 2,1,1; 1,3,5; 2,3,8; 3,4,2
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Distance matrix: rows are sources, columns are destinations.
State at this checkpoint
{ "values": [ 0, 4, 2, "∞", "∞", "∞", 0, "∞", 5, "∞", "∞", 1, 0, 8, "∞", "∞", "∞", "∞", 0, 2, "∞", "∞", "∞", "∞", 0 ], "active": [], "kind": "matrix", "columns": 5 }Step 2: Improve 2 → 3 through 1: 6.
State at this checkpoint
{ "values": [ 0, 4, 2, 9, "∞", "∞", 0, "∞", 5, "∞", "∞", 1, 0, 6, "∞", "∞", "∞", "∞", 0, 2, "∞", "∞", "∞", "∞", 0 ], "active": [ 13 ], "kind": "matrix", "columns": 5 }Step 4: Improve 0 → 3 through 2: 8.
State at this checkpoint
{ "values": [ 0, 3, 2, 8, "∞", "∞", 0, "∞", 5, "∞", "∞", 1, 0, 6, "∞", "∞", "∞", "∞", 0, 2, "∞", "∞", "∞", "∞", 0 ], "active": [ 3 ], "kind": "matrix", "columns": 5 }Step 6: Improve 1 → 4 through 3: 7.
State at this checkpoint
{ "values": [ 0, 3, 2, 8, 10, "∞", 0, "∞", 5, 7, "∞", 1, 0, 6, "∞", "∞", "∞", "∞", 0, 2, "∞", "∞", "∞", "∞", 0 ], "active": [ 9 ], "kind": "matrix", "columns": 5 }Step 8: All-pairs shortest distances. ∞ means no path.
State at this checkpoint
{ "values": [ 0, 3, 2, 8, 10, "∞", 0, "∞", 5, 7, "∞", 1, 0, 6, 8, "∞", "∞", "∞", 0, 2, "∞", "∞", "∞", "∞", 0 ], "active": [], "kind": "matrix", "columns": 5 }
Expected final state
All-pairs shortest distances. ∞ means no path.
Complexity and input bounds
Family: Graphs. Time complexity: O(V³).
Space complexity: O(V squared) distance table.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Directed edges as source,target,weight; separated by semicolons. Nodes 0–7, positive weights 1–99. Start node is 0.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Never add an unreachable sentinel as if it were a finite distance; this playground is not a negative-cycle analyzer.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | // Directed edge arrays from, to, weight; nodes 0..vertices-1; source 0. Up to 8 vertices, 16 edges. Allocate output with at least 256 integers. Positive weights. Writes a row-major vertices × vertices distance matrix; 1000000 denotes unreachable. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(from, to, weight, edges, vertices, output) { for (let i = 0; i < vertices * vertices; i++) { output[i] = 1000000; } for (let i = 0; i < vertices; i++) { output[i * vertices + i] = 0; } for (let i = 0; i < edges; i++) { let index = from[i] * vertices + to[i]; if (weight[i] < output[index]) { output[index] = weight[i]; } } for (let k = 0; k < vertices; k++) { for (let i = 0; i < vertices; i++) { for (let j = 0; j < vertices; j++) { let candidate = output[i * vertices + k] + output[k * vertices + j]; if (candidate < output[i * vertices + j]) { output[i * vertices + j] = candidate; } } } } return 0; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- Algorithm 97: Shortest path
Robert W. Floyd (1962). Research paper.