Dijkstra의 알고리즘이 음의 가중치 모서리에서 작동하지 않는 이유는 무엇입니까?

Dijkstra의 알고리즘이 음의 가중치 모서리에서 작동하지 않는 이유는 무엇입니까?

---

누군가가 단일 소스 최단 경로에 대한 Dijkstra의 알고리즘이 가장자리가 음이 아니어야한다고 가정하는 이유를 말해 줄 수 있습니까?

나는 음의 무게 사이클이 아닌 가장자리 만 이야기하고 있습니다.

---

Dijkstra의 알고리즘에서 일단 정점이 "닫힌"(및 열린 세트에서)으로 표시되면-알고리즘은 최단 경로를 찾았으며이 노드를 다시 개발할 필요가 없습니다. 경로가 가장 짧습니다.

그러나 음수 가중치를 사용하면 사실이 아닐 수 있습니다. 예를 들면 다음과 같습니다.

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

A의 Dijkstra는 먼저 C를 개발하고 나중에 찾지 못할 것입니다. A->B->C

---

조금 더 깊은 설명을 편집 하십시오.

각 이완 단계에서 알고리즘은 "닫힌"노드에 대한 "비용"이 실제로 최소라고 가정하므로 다음에 선택 될 노드도 최소이기 때문에 중요합니다.

그 정점은 다음과 같습니다. 정점에 양수 를 추가하여 비용이 최소가되도록 정점이 열려 있으면 최소값 은 절대 변하지 않습니다.
양수에 대한 제약이 없으면 위의 가정은 사실이 아닙니다.

"닫힌"각 정점을 "알고"있기 때문에 "돌아 보지 않고"이완 단계를 안전하게 수행 할 수 있습니다. "돌아보아야"하는 경우 Bellman-Ford 는 재귀 적 (DP) 솔루션을 제공합니다.

---

소스를 Vertex A로 사용하여 아래에 표시된 그래프를 고려하십시오. 먼저 Dijkstra의 알고리즘을 직접 실행 해보십시오.

설명에서 Dijkstra의 알고리즘을 참조 할 때 아래 구현 된 Dijkstra의 알고리즘에 대해 이야기하겠습니다.

그래서 아웃 시작 값 ( 정점의 소스까지의 거리 이다 초기 각 정점에 할당)을,

먼저 Q = [A, B, C]에서 가장 작은 값을 갖는 정점을 추출합니다 . 즉 A는 그 이후 Q = [B, C] 입니다. 참고 A는 B와 C로 향하고 있으며 둘 다 Q에 있으므로 두 값을 모두 업데이트합니다.

이제 C를 (2 <5)로 추출합니다. 이제 Q = [B] 입니다. C는 아무것도 연결되어 있지 않으므로 line16루프가 실행되지 않습니다.

Finally we extract B, after which . Note B has a directed edge to C but C isn't present in Q therefore we again don't enter the for loop in line16,

So we end up with the distances as

Note how this is wrong as the shortest distance from A to C is 5 + -10 = -5, when you go .

So for this graph Dijkstra's Algorithm wrongly computes the distance from A to C.

This happens because Dijkstra's Algorithm does not try to find a shorter path to vertices which are already extracted from Q.

What the line16 loop is doing is taking the vertex u and saying "hey looks like we can go to v from source via u, is that (alt or alternative) distance any better than the current dist[v] we got? If so lets update dist[v]"

Note that in line16 they check all neighbors v (i.e. a directed edge exists from u to v), of u which are still in Q. In line14 they remove visited notes from Q. So if x is a visited neighbour of u, the path is not even considered as a possible shorter way from source to v.

In our example above, C was a visited neighbour of B, thus the path was not considered, leaving the current shortest path unchanged.

This is actually useful if the edge weights are all positive numbers, because then we wouldn't waste our time considering paths that can't be shorter.

So I say that when running this algorithm if x is extracted from Q before y, then its not possible to find a path - which is shorter. Let me explain this with an example,

As y has just been extracted and x had been extracted before itself, then dist[y] > dist[x] because otherwise y would have been extracted before x. (line 13 min distance first)

And as we already assumed that the edge weights are positive, i.e. length(x,y)>0. So the alternative distance (alt) via y is always sure to be greater, i.e. dist[y] + length(x,y)> dist[x]. So the value of dist[x] would not have been updated even if y was considered as a path to x, thus we conclude that it makes sense to only consider neighbors of y which are still in Q (note comment in line16)

But this thing hinges on our assumption of positive edge length, if length(u,v)<0 then depending on how negative that edge is we might replace the dist[x] after the comparison in line18.

So any dist[x] calculation we make will be incorrect if x is removed before all vertices v - such that x is a neighbour of v with negative edge connecting them - is removed.

Because each of those v vertices is the second last vertex on a potential "better" path from source to x, which is discarded by Dijkstra’s algorithm.

So in the example I gave above, the mistake was because C was removed before B was removed. While that C was a neighbour of B with a negative edge!

Just to clarify, B and C are A's neighbours. B has a single neighbour C and C has no neighbours. length(a,b) is the edge length between the vertices a and b.

---

Dijkstra's algorithm assumes paths can only become 'heavier', so that if you have a path from A to B with a weight of 3, and a path from A to C with a weight of 3, there's no way you can add an edge and get from A to B through C with a weight of less than 3.

This assumption makes the algorithm faster than algorithms that have to take negative weights into account.

---

Correctness of Dijkstra's algorithm:

We have 2 sets of vertices at any step of the algorithm. Set A consists of the vertices to which we have computed the shortest paths. Set B consists of the remaining vertices.

Inductive Hypothesis: At each step we will assume that all previous iterations are correct.

Inductive Step: When we add a vertex V to the set A and set the distance to be dist[V], we must prove that this distance is optimal. If this is not optimal then there must be some other path to the vertex V that is of shorter length.

Suppose this some other path goes through some vertex X.

Now, since dist[V] <= dist[X] , therefore any other path to V will be atleast dist[V] length, unless the graph has negative edge lengths.

Thus for dijkstra's algorithm to work, the edge weights must be non negative.

---

Try Dijkstra's algorithm on the following graph, assuming A is the source node, to see what is happening:

---

Dijkstra의 알고리즘에서 정점이 "닫힌"(및 열린 세트에서)으로 표시되면- 이 노드에서 시작하는 모든 노드가 더 먼 거리로 이어질 것이라고 가정 하므로 알고리즘은 가장 짧은 경로를 찾았으며 이 노드를 다시 개발할 필요는 없지만, 가중치가 음의 경우에는 해당되지 않습니다.

참고 URL : https://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges