Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Solution to 24.4-9 may be wrong #487

Open
Fcber opened this issue Sep 26, 2023 · 0 comments
Open

Solution to 24.4-9 may be wrong #487

Fcber opened this issue Sep 26, 2023 · 0 comments

Comments

@Fcber
Copy link

Fcber commented Sep 26, 2023

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})$.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant