Shortest Path Equality

Question

The following is a proposition found in Ahuja et al Network Flows Book:

Let the vector $d$ represent the shortest path distances. Then a directed path $P$ from the source node to node $j$ is a shortest path if and only if $d(j) = d(i) + c_{ij}$ for every arc $(i,j)$ Where $c_{ij}$ is the length of the arc from $i$ to $j$

Intuitively I understand how it works, however the proposition is left without proof. How should I approach it?

Answer 1

Write the shortest path problem as a linear program with flow variables $x_{i,j}$, construct the dual LP with dual variables $d(i)$, and apply complementary slackness.