# The length of the shortest $s$-$t$ path equals the maximum tenstion between $s$ and $t$

I am stuck at the following exercise:

Consider a directed graph $$G = (V, A)$$ with start vertex $$s ∈ V$$, target vertex $$t \in V$$ and weights $$w_{ij} \in \mathbb{R}$$ for each arc $$(i, j)\in A$$. For any $$i \in V$$ let further be $$\pi_i \in \mathbb{R}$$ be the so-called potential of $$i$$. The potential difference $$\tau_{ij} = \pi_i − \pi_j$$ is called the tension of the arc $$(i, j)$$ with respect to the potential vector $$\pi$$. Finally, let $$\mathcal{P}$$ denote the set of all directed paths from $$s$$ to $$t$$.

Now consider the following LP $$(P)$$: \begin{align} \max& \sum_{(i,j) \in P} \tau_{ij}\\ s.t. & \qquad P \in \mathcal{P} \\ & \qquad \tau_{ij} = \pi_i - \pi_j \text{ for all (i,j) \in A}\\ & \qquad \tau_{ij} \le w_{ij} \text{ for all (i,j) \in A}\\ & \qquad \pi_i \in \mathbb{R} \text{ for all i \in V} \end{align}

If $$P^\ast$$ is a path for which the maximum in $$\mathcal{P}$$ is achieved, the value $$\sum_{(i,j) \in P^\ast} \tau_{ij}$$ is referred to as maximum tension between $$s$$ and $$t$$.

Prove that under the assumption that an $$s$$-$$t$$ shortest path exists with respect to the arc weights $$w_{ij}$$, the length of a shortest $$s$$-$$t$$ path equals the maximum tension between $$s$$ and $$t$$.

If I am not mistaken we have by the definition of $$\tau_{ij}$$ that $$\sum_{(i,j) \in P} \tau_{ij} = \pi_s-\pi_t$$, so the maximal tension is constant for all $$P \in \mathcal{P}$$. Could you please tell me what I am misunderstanding?

Remark: I know that this is supposed to be the dual of the shortest path problem, but I am supposed to do this directly.

• We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. Please revise your question accordingly.
– D.W.
Oct 28 at 22:44

The statement in the exercise, "If $$P^\ast$$ is a path for which the maximum in $$\mathcal{P}$$ is achieved, the value $$\sum_{(i,j) \in P^\ast} \tau_{ij}$$ is referred to as maximum tension between $$s$$ and $$t$$." is indeed quite confusing.
As you have pointed out, given $$i\to\pi_i$$ for all $$i\in V$$ and $$\tau_{ij}=\pi_i-\pi_j$$, we know the sum $$\sum_{(i,j) \in P} \tau_{ij} = \pi_s-\pi_t$$ does not depend on the choice of $$P \in \mathcal{P}$$.
Consider a directed graph $$G = (V, A)$$ with start vertex $$s ∈ V$$, target vertex $$t ∈ V$$ and weights $$w_{ij} \in \mathbb{R}$$ for each arc $$(i, j)\in A$$. Assume there is a path from $$s$$ to $$t$$. Then the maximum tension of $$(G, s, t, w)$$ is the optimal value of the objective function of the the following linear program. When $$G$$ and $$w$$ are understood, we also call it the maximum tension from $$s$$ to $$t$$.
$$\begin{array}{rl} \max&\pi_s-\pi_t\\ s.t. & \pi_i - \pi_j \le w_{ij} \text{ for all }(i,j) \in A\\ & \pi_i \in \mathbb{R} \text{ for all i \in V} \end{array}$$
The essential point here is that the assignment $$\pi_i$$ for all $$i\in V$$ are independent variables in the linear program above.