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 最优最短路径的改进/替代方案,我们将不胜感激?
最佳答案
Yen 的修改在 DAG 上运行良好。事实上,如果你选择线性阶作为 DAG 的拓扑阶,那么它只需要一次迭代就收敛了。你的问题是 Yen 的修改不会解决你的问题,因为它要求边缘以特定顺序而不是同时松弛,这是你需要找到最多 k 边缘的最短路径。
关于algorithm - Yen 对 Bellman-Ford 算法的修改是否适用于 DAG?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25732258/