Dijkstra의 알고리즘을 사용한 음의 가중치

Dijkstra의 알고리즘을 사용한 음의 가중치

---

Dijkstra의 알고리즘이 음의 가중치로 작동하지 않는 이유를 이해하려고합니다. Shortest Paths 에 대한 예제를 읽고 다음 시나리오를 파악하려고합니다.

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

웹 사이트에서 :

모서리가 모두 왼쪽에서 오른쪽으로 향한다고 가정하면 A로 시작하면 Dijkstra의 알고리즘은 d (A, A) + length (edge), 즉 (A, B)를 최소화하는 모서리 (A, x)를 선택합니다. 그런 다음 d (A, B) = 2를 설정하고 d (A, y) + d (y, C)를 최소화하는 다른 모서리 (y, C)를 선택합니다. 유일한 선택은 (A, C)이며 d (A, C) = 3으로 설정됩니다. 그러나 총 길이가 1 인 C를 통해 A에서 B까지의 최단 경로를 찾지 못합니다.

다음 Dijkstra 구현을 사용하여 d [B]가 업데이트되지 않는 이유를 이해할 수 없습니다. 1(알고리즘이 정점 C에 도달하면 B에서 이완을 실행하고 d [B]가 다음과 같은지 확인하여 2업데이트합니다. 값 1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ← Ø
   Q ← V[G]//priority queue by d[v]
   while Q ≠ Ø do
      u ← Extract-Min(Q)
      S ← S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v  V(G)
      d[v] ← ∞
      π[v] ← NIL
   d[s] ← 0
}

Relax(u, v) {
   //update only if we found a strictly shortest path
   if d[v] > d[u] + w(u,v) 
      d[v] ← d[u] + w(u,v)
      π[v] ← u
      Update(Q, v)
}

감사,

Meir

---

제안한 알고리즘은 실제로이 그래프에서 가장 짧은 경로를 찾을 수 있지만 일반적으로 모든 그래프는 아닙니다. 예를 들어 다음 그래프를 고려하십시오.

예에서와 같이 가장자리가 왼쪽에서 오른쪽으로 향한다고 가정합니다.

알고리즘은 다음과 같이 작동합니다.

1. 첫째, 당신은 설정 d(A)에 zero와에 다른 거리 infinity.
2. 그런 다음 노드를 확장 하여 , to 및 로 A설정 합니다 .d(B)1d(C)zerod(D)99
3. 다음으로, C순 변경없이 확장합니다 .
4. You then expand out B, which has no effect.
5. Finally, you expand D, which changes d(B) to -201.

Notice that at the end of this, though, that d(C) is still 0, even though the shortest path to C has length -200. Your algorithm thus fails to accurately compute distances in some cases. Moreover, even if you were to store back pointers saying how to get from each node to the start node A, you'd end taking the wrong path back from C to A.

---

Note, that Dijkstra works even for negative weights, if the Graph has no negative cycles, i.e. cycles whose summed up weight is less than zero.

Of course one might ask, why in the example made by templatetypedef Dijkstra fails even though there are no negative cycles, infact not even cycles. That is because he is using another stop criterion, that holds the algorithm as soon as the target node is reached (or all nodes have been settled once, he did not specify that exactly). In a graph without negative weights this works fine.

If one is using the alternative stop criterion, which stops the algorithm when the priority-queue (heap) runs empty (this stop criterion was also used in the question), then dijkstra will find the correct distance even for graphs with negative weights but without negative cycles.

However, in this case, the asymptotic time bound of dijkstra for graphs without negative cycles is lost. This is because a previously settled node can be reinserted into the heap when a better distance is found due to negative weights. This property is called label correcting.

---

you did not use S anywhere in your algorithm (besides modifying it). the idea of dijkstra is once a vertex is on S, it will not be modified ever again. in this case, once B is inside S, you will not reach it again via C.

this fact ensures the complexity of O(E+VlogV) [otherwise, you will repeat edges more then once, and vertices more then once]

in other words, the algorithm you posted, might not be in O(E+VlogV), as promised by dijkstra's algorithm.

---

Since Dijkstra is a Greedy approach, once a vertice is marked as visited for this loop, it would never be reevaluated again even if there's another path with less cost to reach it later on. And such issue could only happen when negative edges exist in the graph.

---

A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. Assume that you have an objective function that needs to be optimized (either maximized or minimized) at a given point. A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision.

---

Consider what happens if you go back and forth between B and C...voila

(relevant only if the graph is not directed)

Edited: I believe the problem has to do with the fact that the path with AC* can only be better than AB with the existence of negative weight edges, so it doesn't matter where you go after AC, with the assumption of non-negative weight edges it is impossible to find a path better than AB once you chose to reach B after going AC.

---

"2) Can we use Dijksra’s algorithm for shortest paths for graphs with negative weights – one idea can be, calculate the minimum weight value, add a positive value (equal to absolute value of minimum weight value) to all weights and run the Dijksra’s algorithm for the modified graph. Will this algorithm work?"

This absolutely doesn't work unless all shortest paths have same length. For example given a shortest path of length two edges, and after adding absolute value to each edge, then the total path cost is increased by 2 * |max negative weight|. On the other hand another path of length three edges, so the path cost is increased by 3 * |max negative weight|. Hence, all distinct paths are increased by different amounts.

---

TL;DR: For the pseudo code you posted, it works with negative weights.

---

Variants of Dijkstra's Algorithm

The key is there are 3 versions of Dijkstra's algorithm, but all the answers under this question ignore the differences among these variants.

1. Using a nested for-loop to relax vertices. This is the easiest way to implement Dijkstra's algorithm. The time complexity is O(V^2).
2. Priority-queue/heap based implementation + NO re-entrance allowed, where re-entrance means a relaxed vertex can be pushed into the priority-queue again.
3. Priority-queue/heap based implementation + re-entrance allowed.

Version 1 & 2 will fail on graphs with negative weights (if you get the correct answer in such cases, it is just a coincidence), but version 3 still works.

The pseudo code posted under the original question is the version 3 above, so it works with negative weights.

Here is a good reference from Algorithm (4th edition), which says (and contains the java implementation of version 2 & 3 I mentioned above):

Q. Does Dijkstra's algorithm work with negative weights?

A. Yes and no. There are two shortest paths algorithms known as Dijkstra's algorithm, depending on whether a vertex can be enqueued on the priority queue more than once. When the weights are nonnegative, the two versions coincide (as no vertex will be enqueued more than once). The version implemented in DijkstraSP.java (which allows a vertex to be enqueued more than once) is correct in the presence of negative edge weights (but no negative cycles) but its running time is exponential in the worst case. (We note that DijkstraSP.java throws an exception if the edge-weighted digraph has an edge with a negative weight, so that a programmer is not surprised by this exponential behavior.) If we modify DijkstraSP.java so that a vertex cannot be enqueued more than once (e.g., using a marked[] array to mark those vertices that have been relaxed), then the algorithm is guaranteed to run in E log V time but it may yield incorrect results when there are edges with negative weights.

---

자세한 구현 세부 사항 및 Bellman-Ford 알고리즘과 버전 3의 연결에 대해서는 zhihu의 답변을 참조하십시오 . 내 대답이기도하다 (중국어로). 현재는 영어로 번역 할 시간이 없습니다. 누군가가 이것을하고 stackoverflow 에서이 답변을 편집 할 수 있다면 정말 감사합니다.

참고 URL : https://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm