具有负边缘的Dijkstra离开源节点

Question

Dijkstra的算法在图形中失败,我们有负权重的边.然而,对于这个规则有一个例外:如果在有向非循环图中,只有离开源节点的边是负的(所有其他边都是正的),那么我们就可以成功地使用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