Dashboard/Block 4: Flows & Algorithms/Week 12
Week 12Flows & Algorithms

Dijkstra & Bellman-Ford

We study shortest path algorithms for weighted graphs. Dijkstra's algorithm finds shortest paths from a single source in graphs with non-negative weights. Bellman-Ford handles negative weights and detects negative cycles.

Learning Objectives

Implement and trace Dijkstra's algorithm
Implement and trace Bellman-Ford algorithm
Understand when each algorithm is appropriate
Detect negative cycles using Bellman-Ford

Key Concepts

Dijkstra's Algorithm

Dijkstra's algorithm computes shortest paths from a source ss to all other vertices in a graph with non-negative edge weights. It greedily selects the unvisited vertex with smallest tentative distance.

  • -

    Only works with non-negative edge weights

  • -

    Greedy: always process the vertex with smallest current distance

  • -

    With binary heap: O((n+m)log⁡n)O((n + m) \log n)

  • -

    With simple array: O(n2)O(n^2)

Bellman-Ford Algorithm

Bellman-Ford computes shortest paths from a source ss, handling negative edge weights. It relaxes all edges n−1n-1 times. A final pass detects negative cycles.

  • -

    Works with negative weights (unlike Dijkstra)

  • -

    Detects negative cycles (if relaxation possible after n−1n-1 rounds)

  • -

    Time: O(nm)O(nm) — slower than Dijkstra but more general

  • -

    n−1n-1 iterations suffice because shortest paths have at most n−1n-1 edges

W11: Vertex & Edge ConnectivityW13: DFS & Topological Ordering