algorithm - Yen 对 Bellman-Ford 算法的修改是否适用于 DAG？

Question

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

有两个wellknown improvements对于 Bellman-Ford，由于 J. Yen，据说可以将复杂性从 O(|V|^3) 降低到 O(|V|^3/4).. 即，通过等于 1 的常数因子可以很好地节省计算/4(每次改进的 1/2 系数)。

但是，似乎至少有一个修改对有向无环图 (DAG) 没有用，因为 Yen 的方法本质上取决于将图分成两个 DAG，然后改变两个 DAG 之间的迭代，从而获得一个1/2 的优势。是否正确？

同理，如果您能说出 Bellman-Ford 是否还有其他可以找到 k-hop 最优最短路径的改进/替代方案，我们将不胜感激？

Answer 1

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