Dijkstra’s algorithm: the idea
Prerequisites: Nodes, weighted edges, and choosing a minimum.
An edge weight represents a cost, such as time, distance, or fuel. Dijkstra’s algorithm stores a tentative cost for each node. It repeatedly explores the waiting node with the smallest cost. For each neighbor, it adds the edge weight to the current cost. If this candidate improves the neighbor’s cost, it records the new cost and predecessor. With nonnegative weights, a node selected for exploration has its optimal cost.
Try it on the same input
Start at A and aim for I on the “Weighted routes” map. Breadth-first search finds a path with four edges: A → B → D → G → I, with total weight 25. Dijkstra and A* find A → C → E → H → I, also four edges but with total weight 9. Now add an A–I connection with weight 99. Breadth-first search takes that one-edge route; Dijkstra and A* keep the cheaper route.
When to use it—and what to watch
Negative weights invalidate this guarantee. This playground uses positive weights. Without an estimate of where the destination lies, the search may explore many nodes in other directions.
Time and memory
V means the number of nodes; E means the number of edges. O((V + E) log V) with an indexed binary heap. These finite graph searches store visited-node information, predecessors, and a stack or frontier, requiring O(V) search memory.
The executable teaching version deliberately uses arrays: it scans the edge list to find neighbors and, for priority-based searches, sorts the frontier to select a minimum. It therefore does not achieve the adjacency-list or heap bounds quoted above. Recorded playback also stores a snapshot at each operation, using more memory than the search itself. The fixed nine-node graph keeps this small and makes the state easy to inspect.
Reading the display
For frontier-based searches, the frontier contains discovered nodes waiting to be explored. “Previous” records the predecessor used to reach a node. Dashed cyan arrows point back to those predecessors. ∞ means no route to that node has been discovered yet. Pink marks the current node or inspected connection; green marks the completed path. All connections are undirected: you can travel either way.
The Code panel shows explanatory pseudocode. The linked JavaScript is the executable implementation that produces every playback frame. A step can check a condition without changing the table; watch the highlighted line and explanation together.
Continue exploring
- Breadth-first search — Explore one layer at a time. Find a path with the fewest edges.
- A* search — Combine cost so far with an estimate of the journey remaining.
- Depth-first search — Follow one branch deeply, then backtrack when it runs out.
- Bidirectional breadth-first search — Search outward from both endpoints and join where the searches meet.
- Greedy best-first search — Head toward the most promising-looking node, ignoring cost already paid.