In the single-source shortest-paths problem, we want to find the shortest-path weights from a source vertex s to all vertices ν ∈ V. Given a graph G, write a linear program for which the solution has the property that d_ν is the shortest-path weight from s to ν for each vertex ν ∈ V.