A* search: the idea
Prerequisites: Dijkstra’s algorithm and an estimate of remaining cost.
A* orders waiting nodes by f(n) = g(n) + h(n). Here g(n) is the best known cost from the start, and h(n) estimates the remaining cost to the goal. A good estimate directs attention toward promising routes. In this playground, h(n) is the straight-line distance to the goal multiplied by the smallest ratio of edge cost to drawn edge length. Every route costs at least that estimate. The estimate is also consistent: crossing an edge cannot reduce it by more than that edge costs.
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
An estimate that overstates the remaining cost can lose the optimal-path guarantee. This playground recomputes its safe estimate after every weight or connection edit. A weak estimate may provide little advantage over Dijkstra.
Time and memory
V means the number of nodes; E means the number of edges. Depends on the graph, heuristic, and frontier implementation. 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.
- Dijkstra’s algorithm — Explore the cheapest known route first. Minimize total weight.
- 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.