如何证明dijkstra算法在输入图中有负值时不总是有效？
答案:2 悬赏:30 手机版
解决时间 2021-02-03 22:35
- 提问者网友：蔚蓝的太阳
- 2021-02-03 06:38
RT。非常感谢。。很急。
最佳答案
- 五星知识达人网友：想偏头吻你
- 2021-02-03 07:28
反例：
考虑三角形ABC,
A->B = 2 (A到B的距离是2）
A->C = 3
C->B = -2
Dijkstra算法, 以A点为起点
第一步：A->B = 2
第二步：A->C = 3
算法结束
但实际上，A->C->B =1
可以考虑一下Dijkstra不会重新计算已经在路径上的距离。。。希望能帮到你
考虑三角形ABC,
A->B = 2 (A到B的距离是2）
A->C = 3
C->B = -2
Dijkstra算法, 以A点为起点
第一步：A->B = 2
第二步：A->C = 3
算法结束
但实际上，A->C->B =1
可以考虑一下Dijkstra不会重新计算已经在路径上的距离。。。希望能帮到你
全部回答
- 1楼网友：玩家
- 2021-02-03 08:32
你说呢...
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯