algorithm - 如果没有 "processed"检查，Dijkstra 的算法是否适用于负边缘？

Question

通常，在 Dijkstra 算法中，对于每个遇到的节点，我们会在尝试更新其邻居的距离并将它们添加到队列之前检查该节点是否已被处理。这种方法的假设是，如果一个节点的距离被设置一次，那么到该节点的距离在算法的其余部分不能改善，因此如果节点已经被处理过一次，那么到它的邻居的距离就不能改善。但是，对于具有负边的图，情况并非如此。

如果没有负循环，那么如果我们删除“已处理”检查，那么该算法是否总是适用于具有负边的图？

编辑:算法失败的图形示例会很好

编辑 2:Java 代码 https://pastebin.com/LSnfzBW4

用法示例:

3 3 1 <-- 3 nodes, 3 edges, starting point at node 1
1 2 5 <-- edge of node 1 and node 2 with a weight of 5 (unidirectional) 
2 3 -20 <-- more edges
1 3 2

Answer 1

该算法将产生正确的答案，但由于现在可以多次访问节点，因此时间复杂度将呈指数级增长。

这是一个演示指数复杂度的示例:

w(1, 3) = 4
w(1, 2) = 100
w(2, 3) = -100
w(3, 5) = 2
w(3, 4) = 50
w(4, 5) = -50
w(5, 7) = 1
w(5, 6) = 25
w(6, 7) = -25

如果算法试图找到从节点 1 到节点 7 的最短路径，它将首先通过权重为 4 的边到达节点 3，然后探索图的其余部分。然后，它将通过首先转到节点 2 来找到到节点 3 的较短路径，然后它将再次探索图的其余部分。

每次算法到达奇数 inode 之一时，它将首先通过直接边转到下一个奇数 inode 并探索图的其余部分。然后它将通过偶数 inode 找到到下一个奇数 inode 的较短路径，并再次探索图形的其余部分。这意味着每次到达奇数 inode 之一时，图的其余部分将被探索两次，导致至少 O(2^(|V|/2)) 的复杂性。 .