Shortest Paths
Find the lowest-cost path between vertices in a weighted graph.
| Algorithm | Complexity | When to use |
|---|---|---|
O((V + E) log V) |
Single-source, non-negative weights. The default choice. |
|
O((V + E) log V) |
Variant of Dijkstra that uses only the distance map to track visited vertices (no separate color map). Trades a simpler interface / smaller memory footprint for a slightly different visitor protocol. |
|
O(V · E) |
Single-source with negative weights. Detects negative cycles. |
|
O(V + E) |
Single-source on a directed acyclic graph. Fastest possible. |
|
O((V + E) log V) |
Single-source, single-target with a heuristic. Finds the target faster than Dijkstra when a good heuristic is available. |
|
O(V * E + V^2 log V) |
All-pairs on sparse graphs with negative weights. |
|
O(V^3) |
All-pairs on dense graphs. Simple but cubic. |
|
Depends on constraints |
Shortest path with side constraints (e.g. time windows, capacity). |
| Start with Dijkstra. Switch to Bellman-Ford only if you have negative weights. Use A* for single-target queries when you have a distance heuristic (e.g. Euclidean distance on a map). Use DAG shortest paths if your graph is acyclic. |