Shortest Path: LP Formulation

Given a directed graph $G = (N, A)$ with a cost $c_{ij}$ on each arc $(i,j) \in A,$ the shortest path problem asks for a minimum-cost path from a source node $s$ to a sink node $t.$

We model this as a linear program by sending one unit of flow from $s$ to $t.$ For each arc $(i,j) \in A,$ introduce a decision variable

$$x_{ij} \geq 0$$

representing the amount of flow on arc $(i,j).$ The total cost of the flow is

$$\sum_{(i,j)\in A} c_{ij}\, x_{ij},$$

and this is the quantity we minimize.

For example, consider a network with nodes $\{1, 2, 3\}$ and arcs $(1,2),\,(1,3),\,(2,3),$ with costs $c_{12} = 4,$ $c_{13} = 9,$ $c_{23} = 2.$ Taking $s = 1$ and $t = 3,$ the objective is

$$\min \;\; 4 x_{12} + 9 x_{13} + 2 x_{23}.$$

This objective alone is not enough. Without constraints, $\mathbf{x} = \mathbf{0}$ gives cost $0$ at zero flow. We need constraints that force one unit of flow to travel from $s$ to $t.$ Those come next.