Shortest Paths

The question we’re solving

You’re given a weighted graph and a starting vertex (the source) s. Each edge (u,v) has a cost/weight w(u,v). You want, for every vertex v, the shortest-path distance δ(s,v): the minimum total cost of any path from s to v.

A path is a sequence of edges:

s = v₀ → v₁ → … → vₖ = v

Its total cost is the sum of its edge weights:

Then the shortest-path distance is:

If v is unreachable from s, we define δ(s,v) = ∞.

Why shortest paths is more than “like BFS but weighted”

BFS works for unweighted graphs (or all edges cost 1), because “fewest edges” equals “minimum cost.” With weights, a path with more edges can be cheaper.

Example: s→a (cost 100), s→b (1), b→a (1). BFS might pick the 1-edge path s→a, but the cheapest path is s→b→a with cost 2.

So we need algorithms that reason about costs.

Two outputs: distances and predecessors

Most shortest-path algorithms maintain:

• •d[v]: a current estimate of δ(s,v)
• •π[v]: a predecessor pointer used to reconstruct an actual shortest path (a tree rooted at s)

Distances answer “how far,” predecessors answer “how to get there.”

Explicit prerequisite / assumptions block (read this once)

To avoid hidden confusion, here are the working assumptions for the lesson:

1. 1)Directed vs undirected graphs

• •For an undirected edge {u,v} with weight w, treat it as two directed edges (u,v) and (v,u) with the same weight.
• •All algorithms below work on directed graphs; undirected graphs are handled via that conversion.

2. 2)Graph representation

• •We assume an adjacency list representation: for each u, a list of outgoing edges (u,v,w(u,v)).
• •Time bounds are typically written in terms of |V| and |E| using adjacency lists.

3. 3)Edge-weight requirements

• •Dijkstra’s algorithm requires w(u,v) ≥ 0 for every edge reachable from s (practically: assume all edges are nonnegative).
• •Bellman–Ford allows negative edges, but requires no negative-weight cycle reachable from s for distances to be well-defined.

4. 4)Nearby special cases (situating the tools)

• •If the graph is a DAG, shortest paths can be solved in linear time by topological order + relaxation (even with negative edges).
• •If weights are only 0 or 1, 0–1 BFS (deque-based) beats Dijkstra.

These assumptions are the difference between an algorithm that is correct vs. one that silently gives wrong answers.

The “triangle inequality” viewpoint

Shortest paths rests on a basic necessary condition: for any edge (u,v), the true shortest distances must satisfy

Because you can always go to u optimally, then take (u,v). Algorithms exploit this by repeatedly enforcing that inequality via relaxation.

Why relaxation is the heart of shortest paths

Shortest paths feels global (“consider all paths”), but the algorithms work by applying a local rule repeatedly until it forces the global optimum.

That local rule is edge relaxation.

Suppose we currently believe d[u] is a good estimate of δ(s,u). Then taking edge (u,v) suggests a candidate distance to v:

Relaxation says: if this candidate improves d[v], update it.

The relaxation rule (with predecessor)

For a directed edge (u,v):

• •If d[u] + w(u,v) < d[v], then
• •d[v] ← d[u] + w(u,v)
• •π[v] ← u

In pseudocode:

RELAX(u, v):
  if d[u] + w(u,v) < d[v]:
      d[v] = d[u] + w(u,v)
      π[v] = u

Why relaxation makes sense

Relaxation is just enforcing the inequality:

If your current d violates it, you fix d[v].

If eventually you reach a point where no edge can relax, then you have a stable set of estimates. Under the right conditions (depends on algorithm + weights), that stable point equals the true shortest distances.

Initialization matters

Almost all shortest-path methods begin with:

• •d[s] = 0
• •d[v] = ∞ for v ≠ s
• •π[v] = NIL

This encodes: “we know how to reach s at cost 0; everything else unknown.”

A small relaxation walk-through

Take s→a (5), s→b (2), b→a (1). Initialize:

• •d[s]=0, d[a]=∞, d[b]=∞

Relax edges out of s:

• •Relax(s,a): candidate = 0+5=5 < ∞ ⇒ d[a]=5, π[a]=s
• •Relax(s,b): candidate = 0+2=2 < ∞ ⇒ d[b]=2, π[b]=s

Now relax (b,a): candidate = d[b]+1 = 2+1=3 < d[a]=5 ⇒ update d[a]=3, π[a]=b

We discovered a cheaper 2-edge route beating a more direct expensive edge.

Key idea: algorithms differ in how they schedule relaxations

Relaxation is always the operation.

• •Dijkstra is selective: it uses a priority queue to choose the next “most promising” vertex and relaxes outgoing edges from it, relying on nonnegative weights to finalize distances.
• •Bellman–Ford is exhaustive: it repeats relaxing all edges, because negative edges can invalidate greedy finalization.

So when learning shortest paths, keep asking:

1) What relaxations are performed?

2) In what order?

3) When can we stop?

4) When are we allowed to “finalize” a distance?

Why Dijkstra can be greedy

If all edge weights are nonnegative, paths only get more expensive as you extend them. That single fact enables a powerful claim:

When the vertex with smallest current estimate d[·] is selected next, that estimate is already optimal.

This is the extract-min finalization principle.

Intuition: if v currently has the smallest tentative distance, any alternative path to v must go through some not-yet-finalized vertex x with d[x] ≥ d[v]. Adding a nonnegative edge from x onward can’t make a cheaper route to v.

The algorithm shape

Maintain a min-priority queue keyed by d[v]. Often we keep a set S of “finalized” vertices.

1. 1)Initialize d[s]=0, others ∞.
2. 2)Put all vertices into a min-priority queue Q.
3. 3)While Q not empty:

• •u = EXTRACT-MIN(Q) (u has smallest d among not finalized)
• •For each outgoing edge (u,v): RELAX(u,v)
• •If d[v] decreases, perform DECREASE-KEY(Q,v)

Pseudocode sketch:

DIJKSTRA(G, s):
  for v in V:
    d[v] = ∞
    π[v] = NIL
  d[s] = 0

  Q = min-priority-queue over V keyed by d[·]

  while Q not empty:
    u = extract-min(Q)
    for each edge (u,v) in Adj[u]:
      if d[u] + w(u,v) < d[v]:
        d[v] = d[u] + w(u,v)
        π[v] = u
        decrease-key(Q, v)

Correctness idea (why the greedy step is safe)

Let S be the set of extracted vertices so far. Dijkstra maintains the invariant:

• •For every u ∈ S, d[u] = δ(s,u) (final, correct)
• •For every v ∉ S, d[v] is the length of the shortest s→v path that uses only vertices in S internally (frontier estimate)

When we extract-min u, we claim no cheaper path to u exists via vertices not in S. Suppose for contradiction there is a cheaper path P to u that goes through some vertex x ∉ S. Consider the first vertex y on P that is not in S; its predecessor z is in S. When z was finalized, relaxation would set d[y] ≤ d[z]+w(z,y). Because weights are nonnegative, the remainder of the path from y to u can’t reduce the cost below d[y]. This would imply u shouldn’t have been the minimum. Contradiction.

The nonnegativity is used precisely when we say “continuing along the path cannot make it cheaper.” With negative edges, it absolutely can.

Complexity (with adjacency lists)

Let |V| = n, |E| = m.

• •Using a binary heap priority queue:
• •extract-min: O(log n) done n times
• •decrease-key: O(log n) done up to m times
• •Total: O((n + m) log n)

• •Using a Fibonacci heap (advanced): O(n log n + m)

Given the prerequisite includes heaps, the binary heap bound is the one to internalize.

What Dijkstra returns

• •Distances d[v]
• •Predecessors π[v] forming a shortest-path tree for reachable vertices

To reconstruct path to t:

• •follow π[t] backwards until s
• •reverse the sequence

When Dijkstra fails

If there’s a reachable negative edge, the extract-min “finalization” can lock in a distance too early.

Tiny counterexample:

• •s→a (2)
• •s→b (5)
• •b→a (-10)

Dijkstra extracts a first (d[a]=2) and finalizes it. Later, when b is processed, it discovers a cheaper route to a of cost -5, but a is already finalized, so the algorithm (in its standard form) will not correct it. The greedy proof breaks because weights aren’t nonnegative.

So: Dijkstra is fast, but only under the correct weight assumptions.

Why Bellman–Ford exists

Negative edges break greedy finalization, but shortest paths can still be well-defined as long as there is no negative-weight cycle reachable from s.

A negative cycle means you can loop to reduce path cost without bound:

So a correct algorithm must either:

• •compute distances when no negative cycle is reachable, or
• •report that a negative cycle exists

Bellman–Ford does exactly that.

The key fact: shortest paths use at most |V|−1 edges

If there are no negative cycles reachable from s, then an optimal shortest path to any vertex can be chosen to be simple (no repeated vertices). A simple path in a graph with n vertices has at most n−1 edges.

This gives a natural plan:

• •After 1 full pass of relaxing all edges, you know shortest paths using ≤1 edge.
• •After 2 passes, you know shortest paths using ≤2 edges.
• •…
• •After n−1 passes, you know shortest paths using ≤n−1 edges, which is enough.

Bellman–Ford algorithm

Initialize d[s]=0, others ∞.

Repeat n−1 times:

• •for each edge (u,v) in E:
• •RELAX(u,v)

Then do one more pass to detect negative cycles:

• •if any edge can still relax, a negative cycle is reachable.

Pseudocode:

BELLMAN-FORD(G, s):
  for v in V:
    d[v] = ∞
    π[v] = NIL
  d[s] = 0

  for i = 1 to |V|-1:
    for each edge (u,v) in E:
      RELAX(u,v)

  for each edge (u,v) in E:
    if d[u] + w(u,v) < d[v]:
      return "negative cycle reachable"

  return d, π

Why the repeated passes work (a paced invariant)

Define δᵢ(s,v) = the shortest path from s to v using at most i edges.

Claim: after i full passes of relaxing all edges, d[v] = δᵢ(s,v).

• •Base i=0: d[s]=0 and others ∞ matches “0-edge paths.”
• •Step: any ≤(i+1)-edge path to v ends with some edge (u,v), where the prefix to u uses ≤i edges. If after i passes d[u]=δᵢ(s,u), then relaxing (u,v) can set d[v] ≤ d[u]+w(u,v) = cost of that candidate ≤(i+1)-edge path. Taking min over all incoming edges gives δᵢ₊₁(s,v).

After n−1 passes, δₙ₋₁(s,v)=δ(s,v) when no negative cycles are reachable.

Complexity

Bellman–Ford is slower:

• •Outer loop: n−1
• •Inner loop: m edge relaxations

Total time: O(nm)

But it buys you two capabilities Dijkstra doesn’t have:

1. 1)handles negative edges
2. 2)detects negative cycles

Practical improvement: early stopping

In many graphs, distances converge before n−1 passes. You can track whether any relaxation happened in a pass; if none happened, stop early.

This doesn’t change worst-case big-O, but helps in practice.

What about unreachable vertices?

If v is unreachable, d[v] stays ∞ forever.

In the negative-cycle detection pass, edges out of unreachable vertices do not matter because their d[u]=∞, and ∞ + w won’t relax anything.

Summary comparison (at the decision level)

Bellman–Ford is the “safe general tool” for signed weights (no negative cycles). Dijkstra is the fast specialized tool for nonnegative weights.

The skill is choosing based on weight signs and required guarantees.

Algorithm selection guide (with nearby special cases)

Picking the right shortest-path method is mostly about graph structure and edge weights.

Even if you only implement Dijkstra and Bellman–Ford now, keeping the table in mind prevents misapplication.

Path reconstruction (a common “real deliverable”)

Distances are useful, but applications often need the actual route.

Given π[v], reconstruct s→t:

1. 1)Start at t.
2. 2)Repeatedly set t ← π[t] until NIL.
3. 3)Reverse the collected vertices.

If you hit NIL before reaching s, then t was unreachable.

Connection to Network Flow (why shortest paths matters later)

Shortest paths shows up inside flow algorithms in two major ways:

1. 1)Residual graphs and finding augmenting paths

Basic max-flow (like Ford–Fulkerson) repeatedly finds an s→t path in a residual graph. If you choose augmenting paths carefully, you can improve runtime.

2. 2)Min-Cost Max-Flow (advanced but motivating)

A common extension of flow problems is minimizing total cost while sending as much flow as possible. Those algorithms repeatedly compute shortest paths in a residual network where edge costs can be negative due to reverse edges.

That’s where understanding weight-sign applicability becomes essential:

• •Residual networks can introduce negative edges.
• •You may need Bellman–Ford (or Johnson’s reweighting, later) to keep shortest-path computations correct.

So shortest paths is not just a graph topic; it’s a core subroutine that powers more complex optimization.

Mental model to keep

• •Relaxation is enforcing local constraints.
• •Dijkstra works when nonnegativity makes “smallest tentative is final” true.
• •Bellman–Ford works when repeated enforcement up to n−1 edges is enough.

This mental model transfers cleanly into flow, dynamic programming on graphs, and many ML/OR optimization formulations.