最短路径 Dijkstra 算法为什么边上的权值非负阿？

答案:3 悬赏:20

解决时间 2021-04-21 12:36

提问者网友：堕落的邪教徒
2021-04-20 22:07

问个问题自己没搞懂 dijkstra 算法就是求单源最短路径的那个算法嘿嘿牛人给个解答阿

最佳答案

二级知识专家网友：承载所有颓废
2021-04-20 22:25

Dijkstra算法当中将节点分为已求得最短路径的集合（记为S）和未确定最短路径的个集合（记为U），归入S集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与S内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度，而此时a在Dijkstra算法下是无法更新的，由此便可能得不到正确的结果。求带负权值边的单源最短路径可以用贝尔曼-福特算法。

全部回答

1楼网友：你好陌生人
2021-04-21 00:36

可能楼上不知道吧我考的学校出了这么一道题赫赫

2楼网友：如果这是命
2021-04-20 23:13

真厉害啊谢谢

我要举报

如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！