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