前面我们说,Dijkstra 算法不能处理存在负权回路的图,其实,如果一个图仅仅存在负权边,那么 Dijkstra 算法也可能是无法处理的,例如下图,若 A 作为源点,在第一轮循环后,B 被标记数组标记,但我们发现在第二轮循环中,B 还可以通过 C 点继续进行更新。

Dijkstra 算法在实际工程项目中可以说是经常使用的,主要是因为其高效又稳定的时间复杂度。当使用二叉堆作优先队列时,时间复杂度为 $O((m+n)logn)$。

Bellman_Ford 算法可以处理存在负权边的图,也可以判断有无负权回路。它的时间复杂度很稳定,但同时也很高,为 $O(nm)$,在一些实际项目中往往无法让人接受。

SPFA 算法和 Bellman_Ford 算法一样,既可以处理存在负权边的图,也可以判断有无负权回路。但与 Dijkstra 和 Bellman_Ford 算法都不同的是,它的时间复杂度很不稳定,最佳时间复杂度为 $O(n)$,最差时间复杂度为 $O(n^3)$。

总结起来就是下面的表格:

时间复杂度是否可以处理负权边是否可以判断负权回路
Dijkstra 算法$O((m+n)logn)$不可以不可以
Bellman_Ford 算法$O(nm)$可以可以
SPFA 算法$[O(n),O(n^3)]$可以可以

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨 Buy Me A Coffee,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2018-04-02
原文链接:https://ethsonliu.com/2018/04/shortest-path-summary.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。