Shortest Path Problems in Graphs
Survey the major shortest-path algorithms: BFS for unweighted, Dijkstra for non-negative weights, Bellman-Ford for negative weights, and Floyd-Warshall for all pairs. Compare complexity and use cases.
Detailed Explanation
Shortest Path Problems
Finding the shortest path between nodes is one of the most studied problems in computer science. Different graph properties require different algorithms.
Algorithm Selection Guide
| Scenario | Algorithm | Time Complexity |
|---|---|---|
| Unweighted graph | BFS | O(V + E) |
| Non-negative weights | Dijkstra | O((V+E) log V) |
| Negative weights | Bellman-Ford | O(V · E) |
| All pairs | Floyd-Warshall | O(V³) |
| DAG (any weights) | DAG relaxation | O(V + E) |
BFS for Unweighted Graphs
BFS naturally finds shortest paths when all edges have equal weight (or weight 1). It visits nodes in order of distance from the source.
Dijkstra for Non-Negative Weights
Dijkstra's algorithm uses a greedy approach: always process the closest unvisited node. With a priority queue, it efficiently handles sparse graphs.
Bellman-Ford for Negative Weights
Bellman-Ford relaxes all edges V-1 times. It can detect negative cycles (if any distance decreases after V-1 iterations). It is slower but more general than Dijkstra.
Floyd-Warshall for All Pairs
Floyd-Warshall computes shortest paths between all pairs of nodes using dynamic programming. It runs in O(V³) and works with negative weights (but not negative cycles).
DAG Shortest Path
For directed acyclic graphs, topologically sort the nodes first, then relax edges in that order. This runs in O(V + E) even with negative weights.
A* Search
A* extends Dijkstra with a heuristic function h(n) that estimates the remaining distance. When the heuristic is admissible (never overestimates), A* is optimal and often much faster than Dijkstra for single-target queries.
Use Case
GPS navigation systems use Dijkstra or A* to find driving routes. Network protocols like OSPF and IS-IS use shortest-path algorithms for packet routing. Game AI uses A* for character pathfinding on maps. Logistics companies use all-pairs shortest paths to optimize delivery networks across multiple warehouses.