第一个可能存在的问题：因为当负值足够小的时候，根据dijkstra算法的步骤，会更新不存在的边。
我想到一个简明的例子。
假设无穷大是 100，那么所有不存在的边的两点距离都是100，看下图：
当1更新2，把1到2的距离为 -90，1更新3，把1到3的距离变为60。
因为2到3之间没有边，故g[2][3]=100（代表无穷大）,根据dijkstra算法判断，d[3]=60,而d[2]+w=-90+100=10,这时满足条件 d[3]>d[2]+w，于是把d[3]更新成了10，即d[3]=10，这是明显的错误了。
第二个问题：因为每次都是用集合外，到1最小距离的点更新，可能随后有把这个点用负值变小了，但它却没有重新更新。看下图
一开始点1更新了点2和点3，点2的值2，点3的值1.
点3比较小，接着点3更新了点4，点4的值2。这时，点2也是2.
点2更新点3，点3的值变为0，这时，点3却没有更新点4，导致点4的值仍然是2，其实结果应该是1，导致错误。
为什么dijkstra算法中不能存在负权边？
作者：
well188
,
2023-05-08 07:54:36
,
所有人可见
,
阅读 869
well188
,
2023-05-08 07:54:36
,
所有人可见
,
阅读 869
11 评论
x
用邻接矩阵存储不存在的边距离为0啊，不能赋值为无穷。只是dis数组初始先设为无穷表示初始状态源点到其他点距离为无穷。更新时要判断两点距离是否为0再更新，并不会更新不存在的边。
djikstra不能有负权边是因为基于贪心算法，只是选择当前最优，但如果有负权边会有后效性，导致当前最优的选择并不一定是全局最优。
有道理，就是第2个例子的情况。
因为Dijkstra算法在计算最短路径时，不会因为负边的出现而更新已经计算过(收录过)的顶点的路径长度，
这样一来，在存在负边的图中，就可能有某些顶点最终计算出的路径长度不是最短的长度。
这例子有问题吧，你用邻接表存不就行了吗？
好主意，用邻接表可以不用计算不存在的边。但第二个例子仍然存在问题。
这是由于Digkstra是基于贪心实现的
不对吧。d[2]+w=-90+100=10, 无穷+任何数还是无穷。
你说的是理论上，但实际计算的时候，都不是真的无穷大啊，比如0x3f3f3f3f，这也不是一个无穷大，只是在题目中可以充当无穷大。
我说的意思是，在实际的计算中，原本充当无穷大的数，会因为负值导致变小，进而更新本来是无穷大的边。
不是这样的哦
第一种情况可能会出错，但第二种情况必定会出错，所以dijkstra不能有负权边。
比如
d[2] = INF，d[3] = INF,2号点到3号点有一条权值为-10的的边（2−10→3），但是1号点到3号点没有边，这时候d[3] = min(d[3],d[2]+g[2][3])=INF - 10;INF可以是你认为的理论上的正无穷，但是在计算机中只是一个你自己设置的比较大的数值而已，所以可能会造成错误