Graphs
Depth-first search vs Dijkstra's algorithm
Depth-first search and Dijkstra's algorithm both explore a graph, in different ways. Depth-first search: go as deep as possible first, with recursion or a stack. Dijkstra's algorithm: greedy: settle the closest unfinished node first (a simple list as the queue). In the worst case depth-first search takes O(V + E) while Dijkstra's algorithm takes O(V²), so depth-first search scales better on large inputs.
At a glance
| Property | Depth-first search | Dijkstra's algorithm |
|---|---|---|
| Technique | Go as deep as possible first, with recursion or a stack | 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 depth-first search when
you need to explore every path, find connected groups or detect cycles.
Avoid it when
you need the shortest path.
Choose Dijkstra's algorithm when
edges have non-negative weights and you need the cheapest route.
Avoid it when
weights can be negative.