加载中…Dijkstra算法不能有负边
(2011-06-25 16:40:27)
标签：
dijkstrait |
分类： 图论 |
以前一直以为只要没有负环就好了，也蒙过几道题目，今天才意识到在其证明里，如果有负边就会出现错误。
1->22
1->3 100
3->2 -99
用dijkstra求1开始的单源最短路的话因该会得到1->2最短路是2的错误结果
比如
1->2
1->3 100
3->2 -99
用dijkstra求1开始的单源最短路的话因该会得到1->2最短路是2的错误结果
喜欢
0
赠金笔
前一篇：体系结构 测试代码