如果没有 "processed" 检查，Dijkstra 算法是否适用于负边？
Does Dijkstra's algorithm work with negative edges if there is no "processed" check?
通常，在 Dijkstra 的算法中，对于每个遇到的节点，我们会在尝试更新其邻居的距离并将它们添加到队列之前检查该节点是否已被处理。该方法假设如果到一个节点的距离被设置一次，那么到该节点的距离对于算法的其余部分就不能增加，因此如果该节点已经被处理过一次，那么到它的邻居的距离就不能增加。但是，对于具有负边的图，情况并非如此。
如果没有负循环，那么如果我们删除 "processed" 检查，那么该算法是否始终适用于具有负边的图？
编辑：算法失败的图表示例会很好
编辑 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
如果负边从起始节点释放，则 dijkstra 算法有效。但在另一种情况下通常它不适用于负边。
如果我没有正确理解你的问题，我认为这是不可能的。如果没有经过处理的检查，算法将陷入无限循环。例如，对于具有两个节点的双向图，即 a 和 b，一条边从 "a" 到 "b" 或 "b" 到 "a"，它将首先插入节点 "a"在优先级队列中，那么由于"a"到"b"之间有一条边，它会插入节点"b"并弹出节点"a"。然后由于节点 "a" 未标记为节点 "b" 已处理，它将再次将节点 "a" 插入优先级队列中，依此类推。这会导致无限循环。
在具有负边的图中寻找最短路径 Bellmen-ford algorithm 是正确的方法。
该算法将产生正确答案，但由于现在可以多次访问节点，因此时间复杂度将呈指数级增长。
这是一个演示指数复杂度的示例：
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 的更短路径，然后再次探索图中的其余部分。
每次算法到达奇数索引节点之一时，它将首先通过直接边转到下一个奇数索引节点并探索图的其余部分。然后它将通过偶数索引节点找到到下一个奇数索引节点的更短路径，并再次探索图形的其余部分。这意味着每次到达奇数索引节点之一时，图的其余部分将被探索两次，导致至少 O(2^(|V|/2)).
的复杂性
通常，在 Dijkstra 的算法中，对于每个遇到的节点，我们会在尝试更新其邻居的距离并将它们添加到队列之前检查该节点是否已被处理。该方法假设如果到一个节点的距离被设置一次，那么到该节点的距离对于算法的其余部分就不能增加，因此如果该节点已经被处理过一次，那么到它的邻居的距离就不能增加。但是，对于具有负边的图，情况并非如此。
如果没有负循环，那么如果我们删除 "processed" 检查，那么该算法是否始终适用于具有负边的图？
编辑：算法失败的图表示例会很好
编辑 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
如果负边从起始节点释放，则 dijkstra 算法有效。但在另一种情况下通常它不适用于负边。
如果我没有正确理解你的问题，我认为这是不可能的。如果没有经过处理的检查，算法将陷入无限循环。例如，对于具有两个节点的双向图，即 a 和 b，一条边从 "a" 到 "b" 或 "b" 到 "a"，它将首先插入节点 "a"在优先级队列中，那么由于"a"到"b"之间有一条边，它会插入节点"b"并弹出节点"a"。然后由于节点 "a" 未标记为节点 "b" 已处理，它将再次将节点 "a" 插入优先级队列中，依此类推。这会导致无限循环。
在具有负边的图中寻找最短路径 Bellmen-ford algorithm 是正确的方法。
该算法将产生正确答案，但由于现在可以多次访问节点，因此时间复杂度将呈指数级增长。
这是一个演示指数复杂度的示例：
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 的更短路径，然后再次探索图中的其余部分。
每次算法到达奇数索引节点之一时，它将首先通过直接边转到下一个奇数索引节点并探索图的其余部分。然后它将通过偶数索引节点找到到下一个奇数索引节点的更短路径，并再次探索图形的其余部分。这意味着每次到达奇数索引节点之一时，图的其余部分将被探索两次，导致至少 O(2^(|V|/2)).