Bellman-Ford 算法短前导数组
Bellman-Ford Algorithm Short predecessor Array
对 Bellman-Ford 的算法稍加改动：
在第 7 行，我们用 >= 代替不等号，这样它就变成了：
d[v] >= d[u] + w(u,v)
现在我知道了一个事实，它不会改变距离数组，它会给我一个正确的答案。
但它会如何影响第 9 行的前任数组？还会给出正确答案吗？
如果你有非正边，它可能不是一棵树，例如下图，从 n1 开始：
第一关：
- 通过访问 e1：
d[n2] = d[n1] + w[e1] = 1 & p[n2] = n1
- 通过访问 e2：
d[n3] = d[n2] + w[e2] = 1 & p[n3] = n2
- 通过访问 e3：
d[n4] = d[n3] + w[e3] = 1 & p[n4] = n3
- 通过访问 e4：
d[n2] = d[n4] + w[e4] = 1 & p[n2] = n4
并且在所有剩余的遍中，这将重复。所以最后如果你迭代前任例如 n2 你会得到：n2 <- n4 <- n3 <- n2 <- n4 <- ...
但我认为如果你没有非负边，它就可以正常工作。
对 Bellman-Ford 的算法稍加改动：
在第 7 行，我们用 >= 代替不等号，这样它就变成了：
d[v] >= d[u] + w(u,v)
现在我知道了一个事实，它不会改变距离数组，它会给我一个正确的答案。 但它会如何影响第 9 行的前任数组？还会给出正确答案吗？
如果你有非正边，它可能不是一棵树，例如下图，从 n1 开始：
第一关：
- 通过访问 e1：
d[n2] = d[n1] + w[e1] = 1&p[n2] = n1 - 通过访问 e2：
d[n3] = d[n2] + w[e2] = 1&p[n3] = n2 - 通过访问 e3：
d[n4] = d[n3] + w[e3] = 1&p[n4] = n3 - 通过访问 e4：
d[n2] = d[n4] + w[e4] = 1&p[n2] = n4
并且在所有剩余的遍中，这将重复。所以最后如果你迭代前任例如 n2 你会得到：n2 <- n4 <- n3 <- n2 <- n4 <- ...
但我认为如果你没有非负边，它就可以正常工作。