Greedy best-first search: the idea
Prerequisites: A frontier and an estimate of remaining cost.
A heuristic is an estimate used to guide a search. Greedy best-first search selects the waiting node with the smallest estimate of remaining cost, h(n). Unlike A*, it does not add the cost already paid, g(n), to that priority. This playground records the first route to each node and avoids rediscovering it. The table shows that route cost for explanation, but it does not determine exploration order. The estimate uses the same scaled straight-line distance as A*.
Try it on the same input
Add an A–I connection and give it weight 99. Greedy search selects I immediately because its estimated remaining cost is zero, even though the route already costs 99. Switch to A* on the same map: A* considers both cost already paid and estimated cost remaining, and finds the route with total weight 9. On narrow screens the map geometry and estimate change, so intermediate exploration order can differ.
When to use it—and what to watch
Even an estimate that never overstates remaining cost does not make greedy search optimal. It can choose an expensive route that looks close to the destination. This finite graph version avoids cycles and eventually finds a reachable destination; that guarantee does not extend to arbitrary infinite search spaces.
Time and memory
V means the number of nodes; E means the number of edges. O((V + E) log V) with adjacency lists and a binary-heap frontier in this finite, discovery-once graph search. 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
“Route cost” is the cost of the first discovered route, not a guaranteed minimum. The frontier is sorted only by the estimate column. The estimate is a scaled straight-line distance; its numerical value depends on the displayed map geometry.
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.
- 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.