10.22 Analyzing Complexity of Shortest-Path Algorithms
Shortest-path algorithms are often chosen by correctness first, then by complexity.
10.22 Analyzing Complexity of Shortest-Path Algorithms
Shortest-path algorithms are often chosen by correctness first, then by complexity. Once the graph model and edge weights determine which algorithms are valid, the next question is performance.
This recipe explains how to analyze shortest-path algorithms using the two standard graph parameters:
V = number of vertices
E = number of edges
The goal is to understand where the running time comes from, not merely to memorize the final Big O expression.
Problem
Given a shortest-path algorithm, determine its time and space complexity.
For example:
BFS: O(V + E)
Dijkstra: O((V + E) log V)
Bellman-Ford: O(VE)
Floyd-Warshall: O(V³)
These formulas are useful, but only if you understand what each term counts.
Solution
Break the algorithm into operations:
- Initialization
- Vertex processing
- Edge scanning
- Queue or heap operations
- Matrix updates
- Extra storage
Then combine the costs.
For most graph algorithms, the expensive work is either:
Scan every edge
or:
Maintain an ordered frontier
Shortest-path complexity follows from how often those operations occur.
BFS Complexity
BFS uses a queue.
Each vertex is enqueued at most once.
Each adjacency list is scanned at most once.
for head < len(queue) {
v := queue[head]
head++
for _, next := range graph[v] {
...
}
}
The outer loop runs once per reachable vertex.
The inner loops collectively scan all outgoing edges of reachable vertices.
Therefore:
| Component | Cost |
|---|---|
| Initialize distances | O(V) |
| Enqueue each vertex | O(V) |
| Scan adjacency lists | O(E) |
| Total time | O(V + E) |
| Extra memory | O(V) |
For undirected graphs, each edge appears in two adjacency lists. The bound remains:
O(V + E)
because constants are ignored.
Dijkstra Complexity with a Binary Heap
Dijkstra with a binary heap has two main costs:
- Heap operations
- Edge relaxations
Each edge may trigger a heap insertion when using lazy deletion.
if candidate < dist[edge.To] {
dist[edge.To] = candidate
heap.Push(pq, Item{...})
}
There can be up to:
O(E)
heap pushes.
There can also be up to:
O(E)
heap pops, including stale entries.
Each heap operation costs:
O(log E)
or equivalently:
O(log V)
in typical simplified analysis for sparse graphs.
The result is:
| Component | Cost |
|---|---|
| Initialize distances | O(V) |
| Relax edges | O(E) |
| Heap operations | O(E log V) |
| Total time | O((V + E) log V) |
| Extra memory | O(V + E) |
The heap dominates the runtime.
Dijkstra with Linear Scan
A heap is not always necessary.
The linear-scan version repeatedly searches for the unsettled vertex with minimum distance.
for step := 0; step < n; step++ {
v := -1
for i := 0; i < n; i++ {
if !used[i] && (v == -1 || dist[i] < dist[v]) {
v = i
}
}
}
The scan costs:
O(V)
and occurs:
V
times.
So vertex selection costs:
O(V²)
Edge scanning still costs:
O(E)
Total:
| Component | Cost |
|---|---|
| Minimum selection | O(V²) |
| Edge relaxations | O(E) |
| Total time | O(V² + E) |
| Extra memory | O(V) |
For dense graphs, where:
E ≈ V²
this version can be competitive.
Bellman-Ford Complexity
Bellman-Ford relaxes every edge repeatedly.
for i := 0; i < vertices-1; i++ {
for _, edge := range edges {
relax(edge)
}
}
The outer loop runs:
V - 1
times.
The inner loop scans:
E
edges.
So the total cost is:
O(VE)
The final negative-cycle detection pass adds:
O(E)
which does not change the asymptotic bound.
| Component | Cost |
|---|---|
| Relaxation passes | O(VE) |
| Negative-cycle check | O(E) |
| Total time | O(VE) |
| Extra memory | O(V) |
Early termination can improve practical performance, but the worst-case bound remains:
O(VE)
Floyd-Warshall Complexity
Floyd-Warshall uses three nested loops.
for k := 0; k < n; k++ {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
...
}
}
}
Each loop ranges over all vertices.
The number of updates is:
V × V × V
so the runtime is:
O(V³)
The distance matrix stores one entry per ordered pair:
dist[i][j]
so memory is:
O(V²)
| Component | Cost |
|---|---|
| Matrix initialization | O(V²) |
| Triple loop | O(V³) |
| Total time | O(V³) |
| Memory | O(V²) |
Floyd-Warshall is simple, but the cubic term grows quickly.
DAG Shortest Paths Complexity
DAG shortest paths require:
- Topological sort
- One relaxation pass in topological order
Topological sorting scans each vertex and edge once.
O(V + E)
Relaxing outgoing edges also scans each edge once.
O(E)
Total:
| Component | Cost |
|---|---|
| Topological sort | O(V + E) |
| Relax edges | O(E) |
| Total time | O(V + E) |
| Extra memory | O(V) |
This is optimal for a graph traversal algorithm.
0-1 BFS Complexity
0-1 BFS uses a deque.
Each edge relaxation performs constant-time deque operations:
if edge.Weight == 0 {
deque.PushFront(edge.To)
} else {
deque.PushBack(edge.To)
}
With standard distance checks, the algorithm runs in:
O(V + E)
| Component | Cost |
|---|---|
| Deque operations | O(V + E) |
| Edge scans | O(E) |
| Total time | O(V + E) |
| Extra memory | O(V) |
The improvement over Dijkstra comes from replacing heap operations with constant-time deque operations.
Johnson's Algorithm Complexity
Johnson's algorithm combines several phases.
- Bellman-Ford from a super source
- Edge reweighting
- Dijkstra from every vertex
Bellman-Ford:
O(VE)
Reweighting:
O(E)
Dijkstra from every vertex:
V × O(E log V)
=
O(VE log V)
Total:
| Phase | Cost |
|---|---|
| Bellman-Ford | O(VE) |
| Reweighting | O(E) |
| Repeated Dijkstra | O(VE log V) |
| Total | O(VE log V) |
For sparse graphs, Johnson's algorithm can be much faster than Floyd-Warshall.
For dense graphs, it usually loses its advantage.
Sparse Versus Dense Graphs
Graph density changes algorithm choice.
A sparse graph has:
E close to V
A dense graph has:
E close to V²
This matters.
For Dijkstra with a heap:
O((V + E) log V)
On a sparse graph:
O(V log V)
On a dense graph:
O(V² log V)
For linear-scan Dijkstra:
O(V² + E)
On a dense graph:
O(V²)
The supposedly simpler version can be faster for dense graphs because it avoids heap overhead.
Space Complexity
Shortest-path algorithms usually store:
- Distance array
- Parent array
- Visited or settled array
- Queue or heap
- Graph representation
For adjacency lists:
Graph storage = O(V + E)
For adjacency matrices:
Graph storage = O(V²)
Floyd-Warshall requires matrix storage even if the original graph is sparse.
| Structure | Memory |
|---|---|
| Distance array | O(V) |
| Parent array | O(V) |
| Queue | O(V) |
| Heap | O(E) with lazy deletion |
| Adjacency list | O(V + E) |
| Matrix | O(V²) |
Memory often determines feasibility before runtime does.
Practical Scaling
A useful way to reason about growth:
| Complexity | Rough Meaning |
|---|---|
| O(V + E) | Scales to very large graphs |
| O((V + E) log V) | Usually practical for large sparse graphs |
| O(VE) | Expensive except for moderate graphs |
| O(V²) | Acceptable for thousands, risky for millions |
| O(V³) | Acceptable only for smaller graphs |
These are broad guidelines. Constants, memory layout, hardware, and implementation quality matter.
Common Mistakes
Do not count the inner adjacency loop as O(V) automatically. In adjacency-list graphs, all adjacency loops together cost O(E).
Do not ignore heap duplicates in lazy Dijkstra. They can increase heap size to O(E).
Do not treat adjacency matrices and adjacency lists as interchangeable for complexity analysis.
Do not use Floyd-Warshall on sparse graphs merely because it is simpler.
Do not forget that path reconstruction adds memory but usually not significant runtime.
Discussion
Complexity analysis is most useful when it explains design choices.
BFS is fast because each vertex and edge is processed once.
Dijkstra is slower because it maintains an ordered frontier.
Bellman-Ford is slower because it repeats global relaxation passes.
Floyd-Warshall is cubic because it considers every possible intermediate vertex for every ordered pair.
DAG shortest paths are linear because topological order eliminates repeated work.
Understanding these causes makes algorithm selection easier and implementation tradeoffs clearer.
Takeaway
Shortest-path complexity is determined by how often vertices and edges are processed and by the cost of maintaining the frontier. BFS, 0-1 BFS, and DAG shortest paths are linear because they avoid expensive ordering. Dijkstra pays a logarithmic factor for priority-queue ordering. Bellman-Ford pays for repeated edge scans. Floyd-Warshall pays for considering every ordered vertex triple. Once you can identify these sources of cost, the Big O formulas become consequences rather than facts to memorize.