Computer science / GraphsAt your own pace
Find the path.
Understand every decision.
BFS, DFS, Dijkstra and A* on the same graph. Follow the search and discover what choosing the best path means.
BFS
Fewest connections first.
Start at the source. Advance to see how the next node is chosen.
AFinds a path with the fewest connections. When weights differ, that does not guarantee the lowest cost.
Change connections and costsTry your own cases
Saving updates an existing connection or creates a new one. Both directions have the same cost. Zero is allowed; negative costs are not.
A — B8B — D6D — H8A — C2C — E2E — G2G — H2B — E5D — F2F — H3E — F4
See costs and parentsState at this step
| Node | Connections | Parent |
|---|---|---|
| A | 0 | — |
| B | ∞ | — |
| C | ∞ | — |
| D | ∞ | — |
| E | ∞ | — |
| F | ∞ | — |
| G | ∞ | — |
| H | ∞ | — |
Compare all four algorithmsSame start and goal
| Algorithm | Path | Connections | Cost | Nodes |
|---|---|---|---|---|
| BFS | A → B → D → H | 3 | 22 | 7 |
| DFS | A → B → D → F → E → G → H | 6 | 24 | 8 |
| Dijkstra | A → C → E → G → H | 4 | 8 | 7 |
| A* | A → C → E → G → H | 4 | 8 | 5 |
Nodes = selections until reaching the goal or exhausting the search. This does not measure time. BFS minimizes connections; Dijkstra and A* minimize cost. DFS depends on neighbor order.
BFS: Fewest connections first.
Visit in layers. First the start's neighbors, then their neighbors. Mark each node when it enters the queue so it is not added again.
A queue: first in, first out.
What it guarantees
Finds a path with the fewest connections. When weights differ, that does not guarantee the lowest cost.
queue ← [start]
while queue is not empty:
u ← remove first
if u = goal: return path
for each undiscovered neighbor v:
parent[v] ← u; mark v; append to queueNeighbors are checked alphabetically. Dijkstra and A* also break ties alphabetically. This makes the run reproducible; other equally good paths may exist.
Time and memory
With adjacency lists, BFS and DFS visit at most V nodes and E edges: O(V + E), with O(V) auxiliary memory.
To make steps inspectable, this lab sorts an array of priorities and saves state snapshots. It is not an optimized implementation for benchmarking.
Now you decide.
A different case from the explorer. First predict the node; then explain the decision.
BC