Shortest Path Algorithms: Dijkstra's and Bellman-Ford

Terminology

• Shortest path: the path between two vertices in a weighted graph whose total edge weight is minimized.
• Single-source shortest path (SSSP): finding the shortest path from one source vertex to all other vertices in the graph.
• Relaxation: the operation of checking whether a known path to a vertex can be improved by going through another vertex. If $\text{dist}[u] + w(u,v) < \text{dist}[v]$, update $\text{dist}[v]$.
• Negative weight edge: an edge with a negative cost. Dijkstra's algorithm cannot handle these, but Bellman-Ford can.
• Negative weight cycle: a cycle whose total edge weight is negative. If reachable from the source, shortest paths are undefined (you can loop forever to reduce cost).
• Priority queue (min-heap): a data structure that efficiently retrieves the element with the smallest key. Dijkstra's uses this to always process the nearest unvisited vertex.
• Greedy: Dijkstra's algorithm is greedy because it always processes the vertex with the smallest tentative distance, committing to that distance permanently.
• Edge relaxation order: Bellman-Ford relaxes all edges $|V| - 1$ times. This guarantees that shortest paths of up to $|V| - 1$ edges are found, since a shortest path in a graph with no negative cycles has at most $|V| - 1$ edges.

What & Why

Finding the shortest path in a graph is one of the most fundamental problems in computer science. It appears everywhere: GPS navigation, network routing, game AI pathfinding, and social network analysis.

Two algorithms dominate single-source shortest path:

• Dijkstra's algorithm: fast (O((V + E) \log V) with a binary heap), but requires all edge weights to be non-negative
• Bellman-Ford algorithm: slower (O(VE)), but handles negative edge weights and detects negative cycles

The choice between them depends on the graph:

• Non-negative weights? Use Dijkstra's. It is faster and simpler.
• Negative weights possible? Use Bellman-Ford. It is the only correct option.
• Need to detect negative cycles? Bellman-Ford can do this; Dijkstra's cannot.

How It Works

Dijkstra's Algorithm

Dijkstra's maintains a tentative distance for every vertex, initially \infty for all except the source (which is 0). It repeatedly selects the unvisited vertex with the smallest tentative distance, marks it as "finalized," and relaxes all its outgoing edges.

The key insight: once a vertex is finalized, its distance is optimal. This is guaranteed because all edge weights are non-negative, so no future path through an unvisited vertex can produce a shorter route to an already-finalized vertex.

Bellman-Ford Algorithm

Bellman-Ford takes a different approach: it relaxes every edge in the graph, and repeats this |V| - 1 times. After k iterations, all shortest paths using at most k edges are correct. Since a shortest path in a graph with |V| vertices has at most |V| - 1 edges (assuming no negative cycles), |V| - 1 iterations suffice.

After the main loop, one more pass over all edges detects negative cycles: if any edge can still be relaxed, a negative cycle exists.

Why Dijkstra's Fails with Negative Weights

Dijkstra's finalizes vertices greedily: once processed, a vertex's distance is never updated. With negative edges, a later path through a negative edge could produce a shorter distance to an already-finalized vertex. Bellman-Ford avoids this by relaxing all edges repeatedly.

Complexity Analysis

Dijkstra's Analysis

With a binary min-heap, each vertex is extracted once ($O(V \log V)$ total) and each edge triggers at most one decrease-key operation ($O(E \log V)$ total):

For dense graphs ($E = O(V^2)$), this becomes $O(V^2 \log V)$. A Fibonacci heap improves decrease-key to amortized $O(1)$, giving $O(V \log V + E)$.

Bellman-Ford Analysis

The outer loop runs $|V| - 1$ times. Each iteration relaxes all $|E|$ edges:

For sparse graphs ($E = O(V)$), this is $O(V^2)$. For dense graphs ($E = O(V^2)$), this is $O(V^3)$.

Implementation

Dijkstra's Algorithm

ALGORITHM Dijkstra(graph, source)
  INPUT: weighted graph with adjacency list, source vertex
  OUTPUT: dist[] array with shortest distances from source

  CREATE dist array, set all to INFINITY
  CREATE visited array, set all to FALSE
  dist[source] = 0

  CREATE min-priority queue Q
  INSERT (0, source) into Q

  WHILE Q is not empty DO
    (d, u) = EXTRACT_MIN(Q)

    IF visited[u] THEN CONTINUE
    visited[u] = TRUE

    FOR EACH neighbor v of u with edge weight w DO
      IF dist[u] + w < dist[v] THEN
        dist[v] = dist[u] + w
        INSERT (dist[v], v) into Q
      END IF
    END FOR
  END WHILE

  RETURN dist
END

Bellman-Ford Algorithm

ALGORITHM BellmanFord(graph, source, V, E)
  INPUT: graph as edge list, source vertex, V vertices, E edges
  OUTPUT: dist[] array, or report negative cycle

  CREATE dist array of size V, set all to INFINITY
  dist[source] = 0

  // Relax all edges V - 1 times
  FOR i = 1 TO V - 1 DO
    FOR EACH edge (u, v, w) in graph DO
      IF dist[u] != INFINITY AND dist[u] + w < dist[v] THEN
        dist[v] = dist[u] + w
      END IF
    END FOR
  END FOR

  // Check for negative cycles
  FOR EACH edge (u, v, w) in graph DO
    IF dist[u] != INFINITY AND dist[u] + w < dist[v] THEN
      REPORT "Negative weight cycle detected"
      RETURN
    END IF
  END FOR

  RETURN dist
END

Path Reconstruction

ALGORITHM ReconstructPath(parent, source, target)
  INPUT: parent[] array from shortest path algorithm, source and target vertices
  OUTPUT: list of vertices on the shortest path

  path = empty list
  current = target

  WHILE current != source DO
    PREPEND current to path
    current = parent[current]
    IF current = NULL THEN
      RETURN "No path exists"
    END IF
  END WHILE

  PREPEND source to path
  RETURN path
END

Real-World Applications

• GPS navigation: mapping applications use variants of Dijkstra's (with heuristics like A*) to find the fastest route between locations.
• Network routing: OSPF (Open Shortest Path First) uses Dijkstra's algorithm to compute routing tables in IP networks.
• Currency arbitrage detection: Bellman-Ford on a graph of exchange rates (with log-transformed weights) detects negative cycles, which correspond to arbitrage opportunities.
• Game AI: pathfinding in games uses Dijkstra's or A* to navigate characters through weighted terrain (roads are cheap, mountains are expensive).
• Social networks: shortest path algorithms measure "degrees of separation" and influence propagation in social graphs.

Key Takeaways

• Dijkstra's algorithm is the go-to for shortest paths with non-negative weights, running in $O((V + E) \log V)$ with a binary heap
• Bellman-Ford handles negative edge weights at the cost of $O(VE)$ time, and can detect negative weight cycles
• Relaxation is the core operation: check if going through vertex $u$ gives a shorter path to vertex $v$
• Dijkstra's is greedy (finalize the nearest vertex), while Bellman-Ford is DP-like (iterate over all edges $V - 1$ times)
• For most practical applications (road networks, game maps), Dijkstra's with a priority queue is the right choice