Graph Search: BFS, DFS, Dijkstra

BFS explores level by level for shortest paths in unweighted graphs, DFS explores depth-first, and Dijkstra generalizes BFS to weighted graphs.

1. The idea

Breadth-first search (BFS) explores a graph level by level using a queue, and finds shortest paths (fewest edges) in unweighted graphs in $O (V + E)$ time. Depth-first search (DFS) explores as far as possible along each branch before backtracking, using a stack (explicit or via recursion), also $O (V + E)$ , and is well-suited for connectivity, cycle detection, and topological sorting.

Dijkstra's algorithm generalizes BFS to weighted graphs with non-negative edge weights: it greedily expands the unvisited node with the smallest known distance, using a min-heap priority queue, achieving $O ((V + E) lo g V)$ time. It fails with negative edge weights because it doesn't revisit nodes once finalized.

Choice of structure matters: BFS/DFS use $O (V)$ space for visited tracking; Dijkstra additionally needs a priority queue and a distance array, and its complexity is dominated by the heap operations.

2. Why it matters

Graph traversal underlies network/routing problems and appears in quant-dev interviews for tasks like shortest settlement paths, dependency resolution, and connectivity checks.

3. Core mathematics

BFS / DFS time

O (V + E)

Dijkstra time (binary heap)

O ((V + E) lo g V)

BFS shortest path guarantee

correct only for unweighted (or unit-weight) graphs

4. How to recognize it

Think of this when…

Asks for shortest path in an unweighted graph or grid — use BFS
Asks for connectivity, cycle detection, or exploring all paths — consider DFS
Weighted edges with a shortest-path requirement and non-negative weights — use Dijkstra

5. Worked example

Worked example

A graph has 6 nodes and 7 weighted edges (all positive weights). Which algorithm finds the shortest path from node A to all others, and what's its complexity?

1
Weighted graph with non-negative weights and a single-source shortest-path requirement calls for Dijkstra.
$use Dijkstra’s algorithm$
2
Complexity with a binary heap for V=6, E=7.
$O ((V + E) lo g V) = O (13 lo g 6) \approx O (13 \times 2.58)$
Answer: Dijkstra's algorithm, O((V+E) log V) ≈ 34 heap operations worth of work for this small graph — BFS would give wrong answers here since edges are weighted.

6. Common mistakes

Using BFS on a weighted graph expecting correct shortest paths
Applying Dijkstra to graphs with negative edge weights (use Bellman-Ford instead)
Using recursive DFS on very deep graphs without considering stack overflow, when an explicit stack would be safer

7. Quick check

For shortest path in an unweighted graph, the right algorithm is:

Dijkstra's algorithm fails to give correct results when:

8. Practice

2 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Dynamic Programming / Continuation Value

Create a free account to save lesson progress.