Solution to 24.4-9 may be wrong

[Fcber]

The answer only proves

1. Bellman-Ford algorithm maximizes $\min{x_i}$ and
2. Largest value of Bellman-Ford algorithm's result is always $0$

But we cannot draw the conclusion that $(\max{x_i}-\min{x_i})$ is minimized. For there may be a solution with maximum far less than Bellman-Ford algorithm's maximum (i.e. $0$) and minimum slightly less than Bellman-Ford algorithm's minimum, which leads to a less $(\max{x_i}-\min{x_i})$. Here is my solution: Assume $x_{j}=\min{x_i}$ in Bellman-Ford algorithm, and nodes in the shortest path are $v_0,v_{i_1},v_{i_2},...,v_{i_n}$ in order, then we have $x_j=x_{i_n}=\min{x_i}$. As a subpath of $\langle v_0,v_{i_1},v_{i_2},...,v_{i_n}\rangle$, $\langle v_0,v_{i_1}\rangle$ is also a shortest path, which means $\delta(v_0,v_{i_1})=0$ and $x_{i_1}=\max{x_i}$ (for $x_i\le 0$). If $n=1$, which means $\max{x_i}=\min{x_i}=0$, obviously $(\max{x_i}-\min{x_i})$ is minimized for $\max{x_i}\ge \min{x_i}$. Each edge on the shortest path corresponds to a constraint, $$x_{i_{k+1}}-x_{i_k}\le w(v_{i_k},v_{i_{k+1}}),k=1,2,...,n-1$$ Sum from $1$ to $n-1$ and multiply $-1$, we have $$x_{i_1}-x_{i_n}\ge -\sum\limits_{k=1}^{n-1}w(v_{i_k},v_{i_{k+1}})=\delta(v_0,v_{i_1})-\delta(v_0,v_{i_n})$$ Whicherver solution we take, there always two variables $x_{i_1}$ and $x_{i_n}$ have a difference no less than $(\max{x_i}-\min{x_i})$ calculated by Bellman-Ford algorithm, which means Bellman-Ford algorithm minimizes the quantity $(\max{x_i}-\min{x_i})$.