Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 38 ยท Network Flows

Shortest Paths as Flows

Formulate shortest paths as minimum-cost flows, solve them with linprog, compare with Dijkstra and Bellman-Ford, and handle negative arcs, cycles and longest paths in DAGs.

The shortest-path problem asks: what is the cheapest route from a source s to a target t in a weighted network? You may know Dijkstra's algorithm. Here you will see the same problem as a linear program, which is more than a curiosity: it connects shortest paths to duality, lets you add side constraints, and explains why path algorithms work.

The LP formulation

Send exactly one unit of flow from s to t and pay c_ij per unit on each arc. Source has supply 1, target demand 1, and every other node balance 0:

TEXT
minimize    sum c_ij x_ij
subject to  out(i) - in(i) = 1 (i = s), -1 (i = t), 0 otherwise
            x_ij >= 0

Because the constraint matrix is a network matrix (Network Flow Models), the optimal solution is integer, and with a single unit of flow it is a path: x_ij = 1 on the arcs of the shortest route and 0 elsewhere.

Python Shortest path with linprog and with Dijkstra

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both give distance 13, along s, b, a, c, d, t (2 + 1 + 5 + 2 + 3). The agreement is guaranteed because both solve the same problem.

The dual: potentials

The dual of the shortest-path LP is a beautiful picture. Assign a number pi_i to every node, a potential (the distance label), and solve:

TEXT
maximize    pi_t - pi_s
subject to  pi_j - pi_i <= c_ij    for every arc (i, j)

Read the constraint: the potential cannot rise along an arc by more than the arc's cost. The best potentials are exactly the shortest distances from s, since pi_t - pi_s can be raised until some chain of arcs is tight. These tight arcs form the shortest path (duality at work). Dijkstra and Bellman-Ford can be seen as algorithms that build this dual solution.

Complementary slackness tells you the same in words: an arc carries flow only if its dual constraint is tight, that is, if pi_j - pi_i = c_ij.

Negative arc costs

Dijkstra assumes costs are non-negative: once a node is settled, nothing can improve it. With negative arcs it can fail. Bellman-Ford relaxes every arc n - 1 times and works with negative costs. A negative cycle (a loop with negative total cost) makes the problem unbounded: you could circle forever, reducing cost. Bellman-Ford detects it when a further relaxation round still improves a distance. The LP shows the same thing: it comes back unbounded.

Python Bellman-Ford, negative arcs and negative cycles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the first network the shortest route uses the negative arc: s, a, b, t costs 4 - 3 + 2 = 3. After adding b -> a the loop a -> b -> a costs -2 each time, so there is no shortest path and the LP reports status 3 (unbounded).

Longest path in a DAG

In a directed acyclic graph (no cycles) you can find the longest path by negating costs or maximizing. There are no cycles to exploit, so it is well defined. This is exactly the critical path in project scheduling, covered in Critical Path Method. With a topological order it needs only one pass:

TEXT
for each node u in topological order:
    for each arc (u, v, w):  best[v] = max(best[v], best[u] + w)

Side constraints and extensions

An LP formulation lets you add what Dijkstra cannot:

  • Resource-constrained shortest path (minimum cost route with total time at most T): add sum t_ij x_ij <= T. Integrality may be lost, and the problem becomes NP-hard, so you would use integer variables.
  • K shortest paths or disjoint paths: send K units with capacity 1 per arc.
  • Avoid a node: set the capacity of its arcs to 0 or delete them.

Which algorithm should you use?

Situation Method
Non-negative costs, single source Dijkstra, O(E log V) with a heap
Negative costs, no negative cycles Bellman-Ford, O(VE)
DAG Topological order, O(V+E)
All pairs, small graph Floyd-Warshall, O(V^3)
Extra side constraints MILP or specialized labeling algorithms

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the LP model of a shortest path, what are the supplies?

    One unit leaves the source and arrives at the target; intermediate nodes only pass flow through.
  2. 2. What does the LP report when the network contains a negative cycle reachable on the way?

    Circulating around the cycle reduces cost without limit, so no minimum exists.
  3. 3. Which method requires non-negative arc costs?

    Dijkstra settles a node once and never revisits it, which is only safe if later arcs cannot lower the distance.
  4. 4. What do the optimal dual variables (potentials) of the shortest path LP represent?

    They are the distance labels that satisfy pi_j - pi_i <= c_ij, with tight arcs along shortest paths.

Summary

  • A shortest path is a minimum-cost flow of one unit from source to target; the LP solution is integer.
  • The dual maximizes pi_t - pi_s with pi_j - pi_i <= c_ij; optimal potentials are shortest distances.
  • Dijkstra needs non-negative costs; Bellman-Ford handles negatives and detects negative cycles, where the LP is unbounded.
  • Longest paths in DAGs are well defined and give the critical path of a project.
  • The LP view lets you add side constraints at the price of speed and sometimes integrality.

Next: Max Flow and Min Cut