walkccc / CLRS

📚 Solutions to Introduction to Algorithms Third Edition
https://walkccc.me/CLRS
MIT License
4.69k stars 1.26k forks source link

Solution to 24.4-9 may be wrong #487

Open Fcber opened 1 year ago

Fcber commented 1 year ago

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{xi})$. Here is my solution: Assume $x{j}=\min{x_i}$ in Bellman-Ford algorithm, and nodes in the shortest path are $v0,v{i1},v{i2},...,v{i_n}$ in order, then we have $xj=x{i_n}=\min{x_i}$. As a subpath of $\langle v0,v{i1},v{i2},...,v{i_n}\rangle$, $\langle v0,v{i_1}\rangle$ is also a shortest path, which means $\delta(v0,v{i1})=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{xi}$. Each edge on the shortest path corresponds to a constraint, $$x{i{k+1}}-x{ik}\le w(v{ik},v{i{k+1}}),k=1,2,...,n-1$$ Sum from $1$ to $n-1$ and multiply $-1$, we have $$x{i1}-x{in}\ge -\sum\limits{k=1}^{n-1}w(v_{ik},v{i_{k+1}})=\delta(v0,v{i_1})-\delta(v0,v{in})$$ Whicherver solution we take, there always two variables $x{i1}$ 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})$.