algorithm - 带有离开源节点的负边的 Dijkstra

Question

当图中的边具有负权重时，Dijkstra 算法会失败。然而，这条规则有一个异常(exception):如果在有向无环图中只有离开源节点的边为负(所有其他边为正)，那么我们可以成功地使用 Dijkstra 算法。

现在我的问题是，如果在上述异常中图形有一个循环怎么办？我相信 Dijkstra 不会工作，但我无法想出一个有循环的有向图的示例，唯一的负边是那些离开源节点的边，这对 Dijkstra 不起作用。任何人都可以举个例子吗？

Answer 1

在您描述的场景中，Dijkstra 算法可以正常工作。

它在负权重的一般情况下失败的原因是它贪婪地选择在每一步“关闭”哪个节点，并且永远不会重新打开关闭的节点。

现在，假设来源 s有k出边，到k不同的节点。
设它们的顺序为v_1, v_2, ..., v_k (v_1 是最小的)。请注意，对于每个 v_i , v_j这样 i < j - 没有来自 s 的路径至 v_i通过v_j然后“更好”的成本v_i ，因此 - 调查这些第一个节点的顺序永远不会改变。 (并且由于它没有改变，所以在确实找到最短路径之前，以后的节点将无法进入“关闭”状态)。

因此，总的来说 - 没有伤害 - 一旦边缘处于“闭合”状态 - 你永远不会找到它的“更短”路径，因为负边缘仅来自源。

---

在这里我假设 source在你的问题中意味着 d_in(source)=0 ，与 DAG 中的“源”相同。
如果你的意思是在源顶点之外，这可能是一个问题，因为查看一个 2 顶点图使得 w(s,t) = -2, w(t,s)=1 - 图中有一个负循环。所以，为了让上面的解释生效——你必须假设 d_in(s) = 0