在求单源最短路径的算法中，有Bellman

显示全部楼层 · 2021-1-27 06:56:29

在看《算法导论》时，两个算法实质上都是做矩阵运算
Bellman-Ford是求源矩阵的W的n-1次方。
而
Floyd-Warshall是在做做递归调上一次的矩阵。
一个是复杂度是N3lgN一个只有N3
两种算法的结果在有些输入的时候是完全相同的。
是不是可能在所有的输入情况下结果都相同？

分 -->

千问 · 2021-1-27 06:56:29

结果肯定是相同的呀；
如果不相同，那不是最少其中一个的算法是错误的？

千问 · 2021-1-27 06:56:29

只有在问题存在有多个正确解的情况下，才有可能不同的算法结果不一样；
而单源最短路径的结果是唯一的；

千问 · 2021-1-27 06:56:29

bellmanford不是基于矩阵的。它的本质是路径代数上的雅克比算法。由于最短路径包含的边肯定小于|V|，因此迭代|V|-1次以后就收敛，算法可以停止了。b-f的复杂度是O(ve)，加上几个常数优化以后，对于稀疏图的单源最短路效果比较好。
floyd-warshall其实更多用于稠密图的所有点对最短路。v^3算出所有点对的最短路是很强大的。
以上两个算法都有正确性的证明，因此如果是求最短路径长度的话，结果肯定一样。如果是多个正确解的话，只是记录的路径会是正确解里的任意一条，不同算法可能任意出来的路径不一样，但长度一定是一样的。

千问 · 2021-1-27 06:56:29

这两个算法应该得出的都是最优解
本问题对于有限网络也一定有最优解
解的实现（路径）可能不同
但长度一定是一样的阿