当图中的边具有负权重时，Dijkstra 算法会失败。但是，这个规则有一个例外：如果在有向无环图中只有离开源节点的边是负的（所有其他边都是正的），那么我们可以成功地使用 Dijkstra 算法。
现在我的问题是，如果在上述异常中，图表有一个循环怎么办？我相信 Dijkstra 行不通，但我想不出一个有循环的有向图的例子，唯一的负边是那些离开源节点的那些不与 Dijkstra 一起工作的。任何人都可以提出一个例子吗？
问问题
7447 次
1 回答
8
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.
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.
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
于 2012-10-10T00:17:25.460 回答