Dijkstra算法与离开源节点下降沿 [英] Dijkstra with negative edges that leave the source node

问题描述

当在图我们有负权边Dijkstra算法失败。但是，此规则有一个例外：如果在有向无环图只有离开源节点的边缘是负的（所有其他边缘是积极的），那么我们可以成功地使用Dijkstra算法

Dijkstra's Algorithm fails when in a graph we have edges with negative weights. However, to this rule there is an exception: If In a directed acyclic graph only the edges that leave the source node are negative (all the other edges are positive), then we can successfully use Dijkstra's Algorithm.

现在我的问题是，如果在上述异常图有一个周期？我相信，Dijkstra算法是行不通的，但我不能拿出一个有向图，有周期的一个例子，而唯一的负面边缘留下的那些不与Dijkstra算法工作的源节点。任何人都可以提出一个例子吗？

Now my question is, what if in the above exception the graph has a cycle? I believe Dijkstra won't work, but I cannot come up with an example of a directed graph that has cycles, and the only negative edges are those leaving the source node which does not work with Dijkstra. Anyone can suggest an example?

推荐答案

在你描述的情况下，Dijkstra算法将工作得很好。

In the scenario you describe, Dijkstra's algorithm will work just fine.

失败的原因，在一般的情况下用负的重量，因为它贪婪地选择哪个节点为靠近在每一个步骤，和一个封闭的节点是永远不会再开的原因。

The reason why it fails in the general case with negative weight since it greedily chooses which node to "close" at each step, and a closed node is never reopened.

现在，假设源取值的 K 出边，以 K 不同的节点。
让他们的顺序是 V_1，V_2，...，v_k （ V_1 是最小的） 。请注意，对于每个 V_I ， v_j ，使得 I＆LT; Ĵ - 将不会从路径取值到 V_I 到 v_j 有更好的成本则 V_I ，从而 - 调查这些第一节点的顺序不会改变。 （并且由于它不改变，没有办法稍后节点将最短路径之前输入到闭合确实找到）。

Now, assume the source s has k out edges, to k different nodes.
Let the order of them be v_1, v_2, ..., v_k (v_1 being the smallest). Note that for each v_i, v_j such that i < j - there will be no path from s to v_i through v_j with a "better" cost then v_i, thus - the order of investigating these first nodes will never change. (and since it doesn't change, no way a later node will be entered to "closed" before the shortest path is indeed found).

因此​​，在整体 - 是无害的 - 一旦有优势，在封闭 - 你永远不会找到一个短路径，它，因为负边缘只有从源头

Thus, at overall - no harm is done - once an edge is in the "closed" - you will never find a "shorter" path to it, since the negative edges are only from the source.

在这里我假设源在你的问题的手段 D_IN（源）= 0 ，一样的源在DAG。
如果你的意思是出源顶点，它可能是一个问题，因为看一个2阶图，使得 W（S，T）= -2，W（T，S）= 1 - 有一个负循环中的曲线图。因此，以上述解释工作 - 你必须假定 D_IN（S）= 0

In here I assume the source in your question means d_in(source)=0, same as a "source" in a DAG.
If you mean out of the source vertex, it could be a problem since look at a 2 vertices graph such that w(s,t) = -2, w(t,s)=1 - there is a negative cycle in the graph. So, in order to the above explanation to work - you must assume d_in(s) = 0

这篇关于Dijkstra算法与离开源节点下降沿的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！