Graphs
Breadth-first search vs Dijkstra's algorithm
Breadth-first search and Dijkstra's algorithm both explore a graph, in different ways. Breadth-first search: explore level by level with a queue. Dijkstra's algorithm: greedy: settle the closest unfinished node first (a simple list as the queue). In the worst case breadth-first search takes O(V + E) while Dijkstra's algorithm takes O(V²), so breadth-first search scales better on large inputs.
At a glance
| Property | Breadth-first search | Dijkstra's algorithm |
|---|---|---|
| Technique | Explore level by level with a queue | Greedy: settle the closest unfinished node first (a simple list as the queue) |
| Best case time | O(V + E) | O(V²) |
| Average case time | O(V + E) | O(V²) |
| Worst case time | O(V + E) | O(V²) |
| Extra space | O(V) | O(V) |
| Stable (equal values keep their order) | Not applicable | Not applicable |
| In place (no extra array) | Not applicable | Not applicable |
| Needs sorted input | No | No |
When to choose each
Choose breadth-first search when
you need the fewest edges between two nodes, or the nodes level by level.
Avoid it when
the edges have different weights.
Choose Dijkstra's algorithm when
edges have non-negative weights and you need the cheapest route.
Avoid it when
weights can be negative.