Published by Dimitris Kougioumtzis · Updated
Settle the nearest node and relax its outgoing edges.
Settle the smallest tentative distance and relax outgoing edges; nonnegative weights make settled distances final.
When to use Dijkstra shortest paths
Weighted routes with nonnegative costs.
Choosing an alternative
BFS suffices for equal costs; Bellman-Ford uses repeated relaxation.
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: Initial graph.
State at this checkpoint
{ "values": [ "∞", "∞", "∞", "∞", "∞" ], "active": [], "kind": "graph", "visited": [], "chosen": [] }Step 3: Relax 0 → 2; distance = 2.
State at this checkpoint
{ "values": [ 0, 4, 2, "∞", "∞" ], "active": [ 0, 2 ], "kind": "graph", "visited": [ 0 ], "chosen": [] }Step 6: Relax 2 → 3; distance = 10.
State at this checkpoint
{ "values": [ 0, 3, 2, 10, "∞" ], "active": [ 2, 3 ], "kind": "graph", "visited": [ 0, 2 ], "chosen": [] }Step 9: Settle node 3.
State at this checkpoint
{ "values": [ 0, 3, 2, 8, "∞" ], "active": [ 3 ], "kind": "graph", "visited": [ 0, 2, 1, 3 ], "chosen": [] }Step 12: Shortest distances from node 0; ∞ means unreachable.
State at this checkpoint
{ "values": [ 0, 3, 2, 8, 10 ], "active": [], "kind": "graph", "visited": [ 0, 2, 1, 3, 4 ], "chosen": [] }
Expected final state
Shortest distances from node 0; ∞ means unreachable.
Complexity and input bounds
Family: Graphs. Time complexity: O(V² + E).
Space complexity: O(V) distance and settled-state arrays.
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
This playground allows positive weights; negative edges can invalidate greedy settlement.
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 19 | // 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 shortest distances; 1000000 (Python infinity) means 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; i++) { output[i] = 1000000; } output[0] = 0; let seen = Array(256).fill(0); for (let step = 0; step < vertices; step++) { let u = -1; for (let v = 0; v < vertices; v++) { if (seen[v] == 0 && (u == -1 || output[v] < output[u])) { u = v; } } if (u == -1 || output[u] == 1000000) { break; } seen[u] = 1; for (let i = 0; i < edges; i++) { let v = to[i]; if (from[i] == u && output[u] + weight[i] < output[v]) { output[v] = output[u] + weight[i]; } } } 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.
- A note on two problems in connexion with graphs
E. W. Dijkstra (1959). Research paper.