Dijkstra在有向图上具有负边的算法

如果唯一的负边缘成本来自最初的节点呢？ 该算法是否仍然有效？

我觉得是的，因为我想不出一个反例，但我无法证明它。 有反例吗？

对于Dijkstra而言，负边缘是一个问题，因为如果有一个边缘可以稍后选择，而且很大程度上是负值加权的，则无法保证您选取的边缘会产生最短路径。 但是，如果唯一的负边缘从初始节点出来，我不会看到问题。

我不是在寻找一种算法。 我正在寻找对迪克斯特拉的一些见解。

我在谈论一个有向图，如果这有所作为。

反例：

图G =（V，E），其顶点V = {A，B}，边E = {（A，B），（B，A）}，权重函数w（A，B）= -2，w B，A）= +1。

有一个负重量周期，因此最小距离未定义（即使用A作为初始节点）。

具有负面成本优势的麻烦在于，您可以随意多次往返。

如果您强制规定边缘可能不会使用一次以上，则仍然存在问题。 Dijkstra的算法涉及将节点标记为“已访问”，当它与初始节点的距离被认为是一劳永逸的时候。 这发生在所有边被检查之前; 从初始节点到节点X的最短路径已经找到，从初始节点开始的所有其他路径都已经比这更长，没有任何后来发现可以使这些路径更短。 但是如果某处存在负成本边缘，那么稍后的发现可以缩短路径，所以可能存在Dijkstra不会发现的较短路径。

如果只有连接到初始节点的边缘可能会产生负面成本，那么您仍然有问题，因为最短路径可能涉及重新访问初始节点以利用负面成本，这是Dijkstra无法做到的。

如果您强加另一个规则，即一个节点可能不会被访问多次，那么Dijkstra的算法就可以工作。 请注意，在Dijkstra算法中，初始节点的初始距离为零。 如果你给它一些其他的初始距离，算法仍然会找到最短路径 - 但是所有的距离都将被关闭。 （如果你想要最后的真实距离，你必须减去你输入的值。）

A -> B : 6
A -> C : 5
B -> D : 2
B -> E : 1
D -> E : -5
E -> C : -2