Hong Life CalculatorsUnderstanding the graph algorithm running time estimator — concept and principle
Before running a graph algorithm on a large graph, it helps to know whether it will take milliseconds or months. This estimator multiplies out the textbook complexity of four classic graph algorithms for your vertex count V and edge count E, and divides by an assumed speed to give rough run times.
How it is calculated
- BFS / DFS: V + E operations.
- Dijkstra with a binary heap: (V + E) · log₂ V.
- Bellman–Ford: V · E.
- Floyd–Warshall: V³.
- Time = operations ÷ operations per second, shown in ms, s, days or years.
The principle
Breadth-first and depth-first search visit each vertex once and look at each edge a constant number of times, so the work is linear in the size of the graph. Dijkstra's algorithm does the same scan but keeps unfinished vertices in a priority queue; with a binary heap, each update costs O(log V). Bellman–Ford handles negative edge weights by relaxing every edge up to V − 1 times, hence V · E. Floyd–Warshall computes the shortest path between every pair of vertices with three nested loops over V, giving V³ regardless of E. The default 10⁸ operations per second is a cautious figure, since graph code often waits on memory.
Worked example
- Inputs: V = 100,000, E = 1,000,000, 10⁸ operations per second.
- BFS/DFS: 1,100,000 ÷ 10⁸ = 0.011 s = 11 ms.
- Dijkstra: log₂ 100,000 ≈ 16.61, so 1,100,000 × 16.61 ≈ 18,270,000 operations → 183 ms.
- Bellman–Ford: 10⁵ × 10⁶ = 10¹¹ operations → 1,000 s.
- Floyd–Warshall: 10¹⁵ operations → 10⁷ s ÷ 86,400 ≈ 116 days.
| Operations per second | BFS/DFS O(V + E) |
|---|---|
| 2.5e+07 | 44 ms |
| 5e+07 | 22 ms |
| 7.5e+07 | 14.7 ms |
| 1e+08 | 11 ms |
| 1.25e+08 | 8.8 ms |
| 1.5e+08 | 7.33 ms |
| 2e+08 | 5.5 ms |
How to read the result
Anything under a second is fine for one query; if you need thousands of queries, multiply accordingly. Here Dijkstra is the clear choice for single-source shortest paths with non-negative weights. Bellman–Ford is only worth its cost when negative weights are present, and its early-exit version often stops long before V − 1 rounds. Floyd–Warshall is practical only up to a few thousand vertices; on sparse graphs, Dijkstra from every vertex is far cheaper (about 1.8 × 10¹² operations here).
Common mistakes
- Running Dijkstra on graphs with negative weights, which can give wrong answers.
- Ignoring memory: Floyd–Warshall also needs a V × V distance table, 40 GB for 100,000 vertices at 4 bytes each.
- Treating these figures as exact; they ignore constant factors and cache effects.
Frequently asked questions
Is a Fibonacci heap faster for Dijkstra?
In theory it gives O(E + V log V), but in practice binary or pairing heaps are usually faster because of lower constants.
What does BFS find that DFS does not?
BFS finds shortest paths by number of edges in unweighted graphs; DFS is better for cycle detection and topological sorting.
Why is Floyd–Warshall still taught?
It is short, handles negative edges, and is efficient for small dense graphs.
Sources: E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1, 1959 · R. W. Floyd, "Algorithm 97: Shortest path", Communications of the ACM 5(6), 1962 · T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press (graph algorithms)