Dijkstra不能得到含有负权边图的单源最短路径
【Dijkstra不能得到含有负权边图的单源最短路径】对于不含负权边的图求单源最短路径，Dijkstra算法是最高效的。但是在含负权边的图中，Dijkstra很可能得不到正确的结果，因为Dijkstra每次选的是当前能连到的边中权值最小的，在正权图中这种贪心是对的，但是在负权图中就不是这样了。比如1——>2权值为5，1——>3权值为6，3——>2权值为-2，求1到2的最短路径时，Dijkstra就会选择权为5的1——>2，但实际上1——>3——>2才是最优的结果。
文章图片
另外如果包含负环，则意味着最短路径不存在。因为只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。
转载于:https://www.cnblogs.com/tanhehe/archive/2013/02/03/2890767.html
推荐阅读
- 2018-02-06第三天|2018-02-06第三天 不能再了，反思到位就差改变
- 良心
- 不能坚持的理由
- 第十六天（请介绍一件让你非常自豪的事情，（不能是职业类的），什么原因感到自豪。）
- 呼市首大医院温馨提示（男人有啥也不能有“qian”）
- 逃避问题并不能让问题消失
- 在失去中，看见得到的部分！
- 随笔7.21-涂改遗忘
- (If)|(If) 404 Not Found
- 小狗钱钱摘抄