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

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

推荐答案推荐于2017-12-15

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

温馨提示：答案为网友推荐，仅供参考

当前网址：http://11.wendadaohang.com/zd/F7F7qq4P87q884P4PP7.html

其他回答

第1个回答 2013-11-22

规定的吧权值一般都是正数

第2个回答 2013-11-22

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

相似回答

迪杰斯特拉算法为什么不能有负权边答：dijkstra由于是贪心的，每次都找一个距源点最近的点（dmin），然后将该距离定为这个点到源点的最短路径（d[i]<--dmin）；但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点（dmin'），再通过这个负权边L(L<0)，使得路径之和更小（dmin'+L<dmin）,则dmin'+L成为最短路径，...