Yen对Bellman算法的修改适用于DAGs吗？
Yen对Bellman算法的修改适用于DAGs吗？
提问于 2014-09-08 20:03:16
Bellman算法是求解单源最短路径问题的有效算法，它在kth迭代中对每个顶点都有一个独特而有趣的k-跳最优性，这是我的应用程序所必需的。(基本上，我希望在一对顶点之间有一条最多k跳的最短路径)
由于J. Yen的原因，Bellman有两种众所周知的改进，这可以将复杂度从O( the ^3)降低到O(the_x^3/4)。也就是说，在计算中以等于1/4的常数(每项改进的1/2的倍数)节省了很好的费用。
然而，似乎至少有一个修改对于有向无圈图(DAG)没有用，因为Yen的方法本质上取决于将图分成两个DAG，然后改变两个DAG之间的迭代，从而获得1/2的优势。
在同样的路线上，如果您能知道是否有其他改进/替代Bellman可以找到k跳最佳最短路径的话，我们将不胜感激。
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-09-08 20:14:15
对于DAG，Yen的修改效果很好。事实上，如果你选择线性序作为DAG的拓扑序，那么它只在一次迭代中收敛。你的问题是，日元的修改不能解决你的问题，因为它要求边要按特定的顺序而不是同时放松，这就是你需要找到的最短路径，最多有k个边。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/25732258
复制相关文章
相似问题
腾讯云开发者
