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

Question

如果唯一的负边缘成本来自初始节点怎么办？该算法仍然有效吗？

我觉得是的,因为我无法想到反例,但我无法证明这一点.有反例吗？

对于Dijkstra来说,负边是一个问题,因为如果有一条边可以在以后选择,而在很大程度上是负加权,则无法保证您选择的边产生最短路径.但如果唯一的负边缘从初始节点出来,我没有看到问题.

我不是在寻找算法.我正在寻找对Dijkstra的一些见解.

我在谈论有向图,如果这有所不同.

Answer 1

具有负成本优势的麻烦在于,您可以根据需要随意前后移动.

如果您施加的规则不允许多次使用边缘,则仍然存在问题.Dijkstra的算法涉及将节点标记为"已访问",当它与初始节点的距离被认为是一劳永逸时.这发生在检查所有边缘之前; 已经找到从初始节点到节点X的最短路径,来自初始节点的所有其他路径已经比这更长,之后发现的任何路径都不能使这些路径更短.但是如果在某处存在负成本边缘,那么后来的发现可以使路径更短,因此可能存在Dijkstra不会发现的更短路径.

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

如果你强加了另一个规则,即一个节点可能不会被访问多次,那么Dijkstra的算法就可以工作了.请注意,在Dijkstra算法中,初始节点的初始距离为零.如果你给它一些其他的初始距离,算法仍然会找到最短的路径 - 但是所有的距离都会偏离相同的量.(如果你想要最后的实际距离,你必须减去你输入的值.)

1. 所以拿你的图表,称之为A,找到连接到初始节点的任何边缘的最小成本,称之为k,在这种情况下为负值).
2. 通过从连接到初始节点的每条边的成本中减去k,得到一个新的图B. 请注意,所有这些成本现在都是非负的.所以Dijkstra在B上工作.另请注意,B中的最短路径也是A中的最短路径.
3. 将B的初始节点分配距离k,然后运行Dijkstra(这将给出与初始距离为零的运行相同的路径).将此与在A上运行Dijkstra相比较:一旦离开初始节点,两个图中的一切都相同.距离是相同的,决定是相同的,两者将产生相同的路径.在A的情况下,distace是正确的,因为它从零开始.

Answer 2

反例:

图G =(V,E),顶点V = {A,B},边E = {(A,B),(B,A)}和权函数w(A,B)= -2,w( B,A)= +1.

负权重周期为负,因此最小距离未定义(即使使用A作为初始节点).