12.2 Shortest Path Algorithms (Dijkstra's and Bellman-Ford)

Shortest Path Algorithms

Shortest path algorithms solve a fundamental graph problem: given a weighted graph, what's the cheapest way to get from one vertex to another? "Cheapest" here means the path whose edge weights sum to the smallest total.

Two algorithms dominate this space. Dijkstra's algorithm is faster but only works when all edge weights are non-negative. Bellman-Ford is slower but handles negative edge weights and can detect negative cycles. Knowing when to use each one is just as important as knowing how they work.

The Shortest Path Problem

In a weighted graph, each edge has a numeric weight representing some cost: distance in miles, latency in milliseconds, price in dollars, etc. The shortest path between two vertices is the path where the sum of these weights is minimized. This isn't necessarily the path with the fewest edges.

Common applications:

• Navigation systems (Google Maps, Waze): finding the fastest or shortest driving route between two locations
• Network routing: protocols like OSPF use shortest path computations to route packets efficiently across the internet
• Supply chain optimization: minimizing transportation cost or delivery time across a logistics network
• Social networks: measuring degrees of separation between users or finding connection paths for recommendations

Process of Dijkstra's Algorithm

Dijkstra's works by greedily expanding outward from the source, always processing the closest unvisited vertex next. It maintains a running estimate of the shortest distance to every vertex and progressively locks in final answers.

1. Initialize distances. Set the source vertex's distance to 0. Set every other vertex's distance to $\infty$.
2. Insert the source into a priority queue (min-heap), keyed by distance.
3. Extract the minimum. Pull the vertex with the smallest distance from the priority queue. Call it $u$.
4. Relax each neighbor. For every neighbor $v$ of $u$, compute the tentative distance: $\text{dist}(u) + w(u, v)$. If this value is less than $v$'s current distance, update $v$'s distance and record $u$ as $v$'s predecessor. Then insert or update $v$ in the priority queue.
5. Repeat steps 3–4 until the priority queue is empty.

Once the queue is empty, you have the shortest path distances from the source to all reachable vertices. To reconstruct the actual path, trace back through the predecessor pointers.

Process of Bellman-Ford Algorithm

Bellman-Ford takes a different approach: instead of greedily picking the next vertex, it repeatedly relaxes every edge in the graph. It's slower, but this brute-force relaxation handles negative edge weights correctly.

1. Initialize distances. Set the source vertex's distance to 0 and all others to $\infty$.

2. Relax all edges $|V| - 1$ times. Loop $|V| - 1$ iterations. In each iteration, go through every edge $(u, v)$ in the graph. If $\text{dist}(u) + w(u, v) < \text{dist}(v)$, update $\text{dist}(v)$ and set $u$ as $v$'s predecessor.

3. Check for negative cycles. Do one more pass over all edges. If any distance can still be reduced, a negative cycle exists, meaning you can keep looping around it to decrease the total weight forever. In that case, shortest paths are undefined.

4. If no distance was updated in step 3, the algorithm has found the correct shortest paths from the source to all reachable vertices.

Complexities of Shortest Path Algorithms

|Dijkstra's|Bellman-Ford| |---|---|---| |Time complexity|$O((|V|+|E|) \log|V|)$ with a min-heap|$O(|V|\cdot|E|)$| | Negative edge weights | Cannot handle them | Handles them correctly | | Negative cycle detection | No | Yes | |Best used when|All edge weights are non-negative|Negative weights are possible, or you need cycle detection| Dijkstra's gets its time complexity from extracting each vertex from the heap ($O(|V| \log |V|)$) and updating neighbors through edge relaxations ($O(|E| \log |V|)$). With a simple array instead of a heap, the complexity becomes $O(|V|^2)$, which can actually be better for dense graphs.

Bellman-Ford performs $|V| - 1$ passes over all $|E|$ edges, giving $O(|V| \cdot |E|)$. This is noticeably slower than Dijkstra's on large graphs with non-negative weights, so you should default to Dijkstra's when negative weights aren't a concern.

One limitation to keep in mind: Bellman-Ford can only detect negative cycles that are reachable from the source vertex. If a negative cycle exists in a disconnected part of the graph, the standard algorithm won't flag it.