问一下为什么dijkstra算法不能处理负权边.最好举例说明啊,越仔细越好...

lolitacao 1年前 已收到1个回答 举报

dwhro 花朵

共回答了24个问题采纳率:95.8% 举报

会形成环,使得路越走越短,到不了终点.

1年前 追问

5

lolitacao 举报

不是应该每遍历一个点后就放进一个集合,这样最后另外一个集合中不会再有结点了,怎么会死循环....

举报 dwhro

你试试用dijkstra求这个路...因为dijkstra算法所需要的是当前最短路径,也就是说,它所求的必定是最短的,当每条边都是正数时,它可以保证,以后每条边,因为是加法,所以肯定比当前边的值要大,但有负数就不一定了..... 上面那几个数分别是7,5,-5...看的清吗?

lolitacao 举报

会出现错误答案我知道,但是有人说回出现死循环,我觉得不会啊,1->2 1, 2->1 -5, 2->3 7; 有人说上面那个例子是死循环,可我觉得不会出现这个...

举报 dwhro

不会出现啊.....因为被标记了....我记错了... 如果用Bellman_ford会有负权值回路...... dijkstra 不能处理负权边,是因为它无法保证当前所选的边一定是最短边,比如说上面的例子,如果把-5改成5的话,它就可以保证5一定为最短边,因为后面的运算为加法,而如果有负权边的话,后面就变成减了,它就无法保证了....
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.554 s. - webmaster@yulucn.com