Labs / Algorithms & Data Structures

Graph Search & Shortest Path

Compare BFS, DFS, Dijkstra, and A* on weighted terrain. Paint walls or cost-5 mud cells and watch how the explored frontier and chosen path change.

New to this? There\'s a lesson below ↓
← BACK TO LABS
Interactive 2D Graph Arena (Click cells to edit)
Start (S) Goal (G) Wall Mud (Cost 5) Explored Shortest Path
Algorithm & Metrics
NODES EXPLORED
0
TOTAL PATH COST
0
PATH STEPS
0
OPTIMAL COST?
YES
What's happening?
The lesson

Graph Traversal & Shortest Paths: BFS, DFS, Dijkstra, and A*

How frontier data structures (FIFO queue, LIFO stack, min-priority queue) determine search order, edge relaxation, and heuristic optimality.

How the grid represents a graph

A graph G = (V, E) is a set of vertices (nodes) connected by edges. In the grid above, each passable square is a vertex v ∈ V, and each step between adjacent squares (up, down, left, right) is a directed edge (u, v) ∈ E:

  • Walls (black cells): Removed vertices — no edge can enter them.
  • Normal cells (white): Entering the cell has edge weight w(u, v) = 1.
  • Mud cells (amber, marked 5): Entering the cell has edge weight w(u, v) = 5.

Look at the difference between PATH STEPS and TOTAL PATH COST in the simulator metrics:

  • An unweighted shortest path minimizes the number of edges (steps).
  • A weighted shortest path minimizes the sum of edge weights along the path.

Load the MUD PATCH (WEIGHTS) preset and switch between BFS and Dijkstra. BFS takes 14 steps straight through the mud (total cost 34). Dijkstra takes 18 steps around the mud (total cost 18). Both did exactly what they were designed to do: BFS minimized hop count, while Dijkstra minimized total weight.

One core search loop, four data structures

All four algorithms maintain two sets of vertices while searching from S (Start) to G (Goal):

  • Frontier (Open Set): Vertices that have been discovered, but whose neighbors have not all been examined yet.
  • Visited (Closed Set — light blue cells): Vertices that have already been expanded.

In every step, the algorithm removes one vertex u from the Frontier, checks if u = Goal, and adds or updates u's neighbors in the Frontier. The only difference between the four algorithms is the data structure used for the Frontier:

AlgorithmFrontier StructureWhich node is popped next?Time ComplexityOptimal Shortest Path?
BFSFIFO QueueEarliest discovered (shallowest depth d)O(V + E)Yes, on unweighted graphs only
DFSLIFO StackMost recently discovered (deepest branch)O(V + E)No
DijkstraMin-Priority QueueSmallest known cost from Start: g(u)O((V + E) log V)Yes, for non-negative weights (w ≥ 0)
A* SearchMin-Priority QueueSmallest estimated total cost: f(u) = g(u) + h(u)O((V + E) log V)Yes, if heuristic h(u) is admissible

1. Breadth-First Search (BFS) and Depth-First Search (DFS)

Click CLEAR GRID (so all edge weights are 1) and compare BFS and DFS:

BFS uses a First-In, First-Out (FIFO) queue. Because vertices are examined in the exact order they are discovered, BFS explores all vertices at distance d = 1 from Start, then all vertices at d = 2, then d = 3, expanding outward in layers. The first time BFS reaches the Goal, it is guaranteed to have found a path with the minimum number of edges. However, because a FIFO queue never looks at edge weights, BFS treats a cost-5 mud step the same as a cost-1 step.

DFS uses a Last-In, First-Out (LIFO) stack. Whenever it discovers a neighbor, it immediately follows that neighbor deeper before exploring other branches at the current depth, backtracking only when it hits a dead end. Click the CORRIDORS preset and select DFS: notice how it snakes up and down full columns, returning a non-optimal path. (In practice, DFS is used for cycle detection, topological sorting, and connected components rather than shortest paths.)

2. Dijkstra's Algorithm and Edge Relaxation

When edges have different weights, the shortest path is no longer the one with the fewest steps. Dijkstra's algorithm tracks a distance table g[v] — the best cost found so far from Start to each vertex v:

1. Set g[Start] = 0, and g[v] = ∞ for all other vertices.
2. Push (Start, g = 0) into a Min-Priority Queue.
3. While the priority queue is not empty:
     Pop vertex u with the smallest g[u].
     For each neighbor v of u with edge weight w(u, v):
       if g[u] + w(u, v) < g[v]:          // Edge Relaxation
         g[v] = g[u] + w(u, v)
         parent[v] = u
         Push (v, g[v]) into the priority queue.

The test if g[u] + w(u, v) < g[v] is called edge relaxation: we check whether going through u improves the best known cost to v. Because all edge weights are non-negative (w ≥ 0), the moment a vertex u is popped with the minimum g[u] in the queue, no future detour through another vertex could ever make g[u] smaller.

3. A* Search and Admissible Heuristics

Click BARRIER WALL and select Dijkstra. Look at the light-blue Visited cells: Dijkstra expands equally in all directions — including the cells to the left of Start, directly away from the Goal — because g(u) only measures distance from Start.

A* Search guides the priority queue toward the Goal by ordering vertices by:

f(u) = g(u) + h(u)
  • g(u) is the exact cost from Start to u (just like Dijkstra).
  • h(u) is the heuristic estimate of the remaining cost from u to Goal. On a 4-direction grid (no diagonal moves), the standard heuristic is the Manhattan distance: h(u) = |u.row − goal.row| + |u.col − goal.col|.

Switch the dropdown from Dijkstra to A* Search on the Barrier Wall preset. Both find a path of cost 18, but A* explores roughly half as many vertices because stepping away from the Goal increases both g(u) and h(u), pushing backward cells to the back of the priority queue.

When does A* guarantee an optimal path? The heuristic h(u) must be admissible — meaning it never overestimates the true minimum cost to reach the Goal (0 ≤ h(u) ≤ h*(u)). Since every step on our grid costs at least 1, you can never reach the Goal in less than the Manhattan distance, so Manhattan distance is strictly admissible. (Notice that if you set h(u) = 0 everywhere, f(u) = g(u) and A* becomes Dijkstra's algorithm.)

Exercises

1. Load MUD PATCH (WEIGHTS) and compare BFS, Dijkstra, and A*. Record Path Steps, Total Path Cost, and Nodes Explored for all three.

Show solution
  • BFS: 14 steps, cost 34 (walks straight through six cost-5 mud cells: 8×1 + 6×5 = 38, or 10×1 + 4×5 = 30 depending on entry; in this grid 4 mud cells + 14 steps = cost 34).
  • Dijkstra: 18 steps, cost 18 (detours around the mud on weight-1 cells), explores ~168 nodes.
  • A*: 18 steps, cost 18 (same optimal path), explores ~52 nodes.

2. Why does Dijkstra's algorithm fail if a graph has negative edge weights?

Show solution
Dijkstra assumes that adding more edges to a path can only increase (or keep equal) its total cost, so the minimum-g(u) vertex popped from the priority queue is final. If a negative edge exists later in the graph, a longer path could suddenly become cheaper after u was already finalized. Graphs with negative weights require the Bellman-Ford algorithm.

Quiz

Why does BFS return a path of cost 34 on the Mud Patch preset while Dijkstra returns a path of cost 18?

What condition must the heuristic function h(u) satisfy for A* to guarantee an optimal shortest path?

In Dijkstra's algorithm, what is the "edge relaxation" step for an edge (u, v) of weight w?

If you set the heuristic h(u) = 0 for every vertex in A* Search, which algorithm does A* become?