Dijkstra不能得到含有负权边图的单源最短路径

【Dijkstra不能得到含有负权边图的单源最短路径】对于不含负权边的图求单源最短路径,Dijkstra算法是最高效的。但是在含负权边的图中,Dijkstra很可能得不到正确的结果,因为Dijkstra每次选的是当前能连到的边中权值最小的,在正权图中这种贪心是对的,但是在负权图中就不是这样了。比如1——>2权值为5,1——>3权值为6,3——>2权值为-2,求1到2的最短路径时,Dijkstra就会选择权为5的1——>2,但实际上1——>3——>2才是最优的结果。
Dijkstra不能得到含有负权边图的单源最短路径
文章图片


另外如果包含负环,则意味着最短路径不存在。因为只要在负权回路上不断兜圈子,所得的最短路长度可以任意小。

转载于:https://www.cnblogs.com/tanhehe/archive/2013/02/03/2890767.html

    推荐阅读