$\min \sum c_{uv}f_{uv}$
s.t.
$\sum_v f_{uv} \le s_u \quad \forall u$
$\sum_u f_{uv} \ge d_v \quad \forall v$
$f_{uv} \ge 0 \quad\quad \forall (u,v)$
Using Konig's Theorem (hint: what bipartite are you going to use?), prove the Konig-Egervary Theorem: the maximum size of an independent set of 0s (i.e., the maximum such $Z$) equals the minimum number of lines that cover all all 0s.
Recall also the string model of the shortest path problem's dual, where given an undirected graph, we cut a piece of string of length equal to each edge, tie the strings together where they meet at nodes, and, say, attach a marble at each knot.
We know the maximum distance $s$ and $t$ knots can be pulled apart turns out to be the length of the shortest path. Describe a (very) simple physical procedure you could carry out with the string/marble graph apparatus, which would perform or implement the primal-dual algorithm. Explain what events occurring over the course of this procedure correspond to cycles in the primal-dual algorithm's loop (i.e., the closing of new nodes).