0

Bellman-Ford 算法对于解决单源最短路径问题很有用，并且在第 k 次迭代时，它具有一个独特而有趣的特性，即每个顶点的 k-hops 最优性，这是我的应用程序所必需的。（基本上，我想要一对顶点之间最多 k 跳的最短路径）

由于 J. Yen，Bellman-Ford有两个众所周知的改进，据说可以将复杂度从 O(|V|^3) 降低到 O(|V|^3 /4)。常数因子等于 1/4（每次改进的因子为 1/2）。

然而，似乎至少有一个修改对有向无环图 (DAG) 没有用，因为 Yen 的方法本质上依赖于将图划分为两个 DAG，然后改变两个 DAG 之间的迭代，从而获得1/2 的系数。这是对的吗？

同样，如果您能说出 Bellman-Ford 是否有任何其他改进/替代方案可以找到 k-hop 最佳最短路径，将不胜感激？

4

1 回答 1

2

Yen 的修改在 DAG 上运行良好。实际上，如果选择线性顺序作为 DAG 的拓扑顺序，那么它只需一次迭代即可收敛。对您而言，问题是 Yen 的修改不会解决您的问题，因为它需要以特定顺序而不是同时放松边缘，这就是您需要找到最多 k 个边缘的最短路径。

于 2014-09-08T20:14:15.317 回答