Dashboard/Block 3: Graph Algorithms/Week 8
Week 8Graph Algorithms

Shortest Paths

Last week we found shortest paths in unweighted graphs using BFS. But what if edges have different weights — like roads with different distances or network links with different latencies? This week covers two classic algorithms for weighted shortest paths. Dijkstra's algorithm is the go-to choice when all edge weights are non-negative: it greedily processes the closest unvisited vertex and 'relaxes' its neighbors, running efficiently with a priority queue. Bellman-Ford is slower but more powerful: it handles negative edge weights and can detect 'negative weight cycles' (loops where going around actually decreases total distance, making shortest paths undefined). Understanding when to use which algorithm is crucial for real-world applications like GPS navigation, network routing, and logistics optimization.

Learning Objectives

Implement Dijkstra's algorithm using a min-priority queue (heap), understanding the 'relaxation' step where you check if going through a newly processed vertex offers a shorter path
Understand why Dijkstra's algorithm fails with negative edge weights — its greedy approach permanently locks in distances that might later be proven wrong by a negative edge
Implement the Bellman-Ford algorithm, which handles negative edges by relaxing all edges V-1 times (since the longest shortest path has at most V-1 edges)
Detect negative weight cycles using Bellman-Ford's extra pass — if any distance still decreases after V-1 rounds, a negative cycle exists and shortest paths are undefined

Key Concepts

Dijkstra's Algorithm

Dijkstra's algorithm is the most famous shortest-path algorithm and is used in GPS navigation, network routing, and many other real-world systems. It works on graphs where all edge weights are non-negative (no negative distances). The idea is greedy: maintain a 'tentative distance' for every vertex (initially infinity for all except the source, which is 0), then repeatedly pick the unvisited vertex with the smallest tentative distance, mark it as 'finalized,' and update (relax) the distances of its neighbors. The key insight is that once a vertex's distance is finalized, it will never change — which is only true when there are no negative edges. Using a binary min-heap as the priority queue, the algorithm runs in O((V+E) log V) time.

  • -

    Greedy approach: always finalize the unvisited vertex with the smallest tentative distance — this vertex's shortest path is now guaranteed correct (assuming no negative edges)

  • -

    Does NOT work with negative edge weights — a negative edge could provide a shorter path to an already-finalized vertex, but Dijkstra never revisits finalized vertices

  • -

    With a binary min-heap: O((V+E) log V) — V extract-min operations and up to E decrease-key operations, each costing O(log V)

  • -

    With a Fibonacci heap (theoretical improvement): O(V log V + E) — decrease-key becomes O(1) amortized

  • -

    Relaxation is the core operation: for each neighbor v of the current vertex u, check if d[u] + w(u,v) < d[v] — if so, update d[v] to the shorter distance

  • -

    ⚠ Common mistake: Applying Dijkstra to graphs with negative edges. It will give WRONG answers because it permanently finalizes distances that might later be improved via a negative edge. Use Bellman-Ford for negative weights.

  • -

    ⚠ Common mistake: Confusing Dijkstra's key (total distance from source) with Prim's key (edge weight to the MST). They use the same priority-queue structure but track completely different values.

Bellman-Ford Algorithm

Bellman-Ford is a more general shortest-path algorithm that works even when some edges have negative weights. The idea is simple but powerful: repeat V-1 times — in each round, go through every edge in the graph and try to 'relax' it (check if using this edge gives a shorter path). After V-1 rounds, all shortest paths are guaranteed to be found because the longest possible shortest path in a graph with V vertices has at most V-1 edges. But Bellman-Ford has a bonus feature: after the V-1 rounds, do one more round. If any distance still decreases, it means there is a 'negative weight cycle' — a loop where the total edge weight is negative, meaning you could keep going around forever to get infinitely negative path lengths. In this case, shortest paths are undefined. Bellman-Ford runs in O(V·E) time, which is slower than Dijkstra, so use Dijkstra when all weights are non-negative.

  • -

    Works correctly with negative edge weights, unlike Dijkstra — this makes it essential for graphs where costs can decrease (e.g., currency exchange arbitrage detection)

  • -

    V-1 relaxation passes are sufficient because any shortest path in a graph with V vertices contains at most V-1 edges (otherwise it would revisit a vertex, forming a cycle)

  • -

    The V-th pass detects negative weight cycles: if any distance still decreases, a negative cycle exists and there is no well-defined shortest path

  • -

    Slower than Dijkstra (O(V·E) vs O((V+E) log V)), so only use Bellman-Ford when negative edges are present or when you need cycle detection

W7: Graph Basics & TraversalsW9: Minimum Spanning Trees