Find a way through
Same map, six ways to search. Step through an algorithm, then switch to another to see what changes. Select a node to change the destination; select a connection to edit its weight.
Edit the graph
Select a connection in the map to edit it. Select any node to make it the destination. The dropdowns also work with a keyboard.
What are we solving?
A graph is a collection of nodes (the labeled circles) and edges (their connections). Here, each edge has a positive weight representing travel cost. We want a route from a starting node to a destination.
| Algorithm | Chooses next node by | Finds |
|---|---|---|
| Breadth-first search | Discovery order | Fewest edges |
| Dijkstra | Lowest cost so far | Lowest total weight |
| A* | Lowest cost so far + estimate remaining | Lowest total weight with the safe estimate used here |
| Depth-first search | One unvisited neighbor at a time; backtrack on exhaustion | A path, without a shortest-path guarantee |
| Bidirectional BFS | Alternating complete layers from both ends | Fewest edges |
| Greedy best-first | Lowest remaining estimate only | A path, without a cheapest-path guarantee |
Explore the lessons
- 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.
- Greedy best-first search — Head toward the most promising-looking node, ignoring cost already paid.
A revealing experiment
Add an A–I connection and set its weight to 99. Breadth-first search chooses that single connection. Dijkstra and A* take a longer route with a lower total cost. Greedy search chooses the expensive shortcut because its remaining estimate is zero. Then choose “Equal costs” to see why breadth-first search works well when every move costs the same.
Try the “Unreachable destination” map to watch a search exhaust its frontier. Or set the start and destination to the same node: the solution needs no connections.