如果仅有起始节点的边具有负权值，那么Dijkstra算法是否仍然有效？
我认为是有效的，因为我无法想到反例，但我很难证明。是否存在反例？
对于Dijkstra算法而言，负权边是一个问题，因为不能保证选择的边会产生最短路径，如果后面有一条较大的负权边可选。但如果仅有起始节点的边具有负权值，我不认为有问题。
我不是在寻找一个算法，而是在寻找有关Dijkstra算法的见解。
我谈论的是一个有向图，如果有区别的话。
3个回答
21
具有负成本边的问题在于，您可以沿着它来回走无数次。
如果您规定一条边不能重复使用，则仍然存在问题。 Dijkstra算法涉及将节点标记为“已访问”，当从初始节点到该节点的距离被认为已知时进行标记。这发生在所有边都未被检查之前；已经找到了从初始节点到节点X的最短路径，从初始节点到所有其他路径都比该路径长，后来发现的任何东西都不能使这些路径变得更短。但是，如果某处存在负成本边缘，那么稍后的发现可能会使路径变短，因此可能存在Dijkstra无法发现的更短路径。
如果只有连接到初始节点的边可以具有负成本，则仍然存在问题，因为最短路径可能涉及重新访问初始节点以利用负成本，这是Dijkstra无法做到的。
如果您强制执行另一个规则，即一个节点不能被访问多次，则Dijkstra算法将起作用。请注意，在Dijkstra算法中，初始节点被赋予零的初始距离。如果您给它其他初始距离，算法仍会找到最短路径-但是所有距离都会偏离相同的量。 （如果您想在结束时得到真实距离，则必须减去您输入的值。）
因此，取出您的图形，称之为A，找到与初始节点相连的任何边的最小成本，称之为k，在这种情况下为负数。
制作一个新图B，通过从连接到初始节点的每条边缘的成本中减去k来获得它。请注意，现在所有这些成本都是非负的。因此，Dijkstra在B上工作。还要注意，B中的最短路径也是A中的最短路径。将起点节点B的距离设为k，然后运行Dijkstra算法（这将得到与将初始距离设为零时相同的路径）。将其与 naively 运行 A 的 Dijkstra 算法作比较：一旦离开初始节点，两个图形中的everything's the same。距离相同，决策相同，两者会产生相同的路径。对于A的情况下，距离将是正确的，因为它从零开始。
如果您规定一条边不能重复使用，则仍然存在问题。 Dijkstra算法涉及将节点标记为“已访问”，当从初始节点到该节点的距离被认为已知时进行标记。这发生在所有边都未被检查之前；已经找到了从初始节点到节点X的最短路径，从初始节点到所有其他路径都比该路径长，后来发现的任何东西都不能使这些路径变得更短。但是，如果某处存在负成本边缘，那么稍后的发现可能会使路径变短，因此可能存在Dijkstra无法发现的更短路径。
如果只有连接到初始节点的边可以具有负成本，则仍然存在问题，因为最短路径可能涉及重新访问初始节点以利用负成本，这是Dijkstra无法做到的。
如果您强制执行另一个规则，即一个节点不能被访问多次，则Dijkstra算法将起作用。请注意，在Dijkstra算法中，初始节点被赋予零的初始距离。如果您给它其他初始距离，算法仍会找到最短路径-但是所有距离都会偏离相同的量。 （如果您想在结束时得到真实距离，则必须减去您输入的值。）
因此，取出您的图形，称之为A，找到与初始节点相连的任何边的最小成本，称之为k，在这种情况下为负数。
制作一个新图B，通过从连接到初始节点的每条边缘的成本中减去k来获得它。请注意，现在所有这些成本都是非负的。因此，Dijkstra在B上工作。还要注意，B中的最短路径也是A中的最短路径。
- Beta
12
反例:
图 G = (V, E)，其中 V = {A, B}，边 E = {(A, B), (B, A)}，权重函数 w(A, B) = -2，w(B, A) = +1。
存在负权环，因此无法确定最小距离（即使以 A 作为起始节点）。
- Sheldon L. Cooper
2
1Dijkstra算法会告诉你从A到B的最小权重路径是[A，B]，权重为-2。但是从A到B还有比这更小权重的路径，例如[A，B，A，B]，权重为-3。 - Sheldon L. Cooper
标记为答案，因为我要求提供反例或证明。 - user438293456
0
Dijkstra算法不能正确处理带有负边权的图（即使该图没有任何负权重环）。例如，对于以下以源顶点A为起点的图，它计算出了(A,C)之间不正确的最短路径值。
A -> B : 6
A -> C : 5
B -> D : 2
B -> E : 1
D -> E : -5
E -> C : -2
- DanglingPointer
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接