해당 글은 Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani를 정리한 스터디 노트입니다. 해석하면서 정리한 글입니다.

4.6 Shortest paths in the presence of negative edges

4.6.1 Negative edges

Dijkstra’s algorithm이 부분적으로 동작하는 이유는 시점(s)부터 어떤 노드 v로 가는 가장 짧은 경로는 v보다 가까운 노드들만 지나가기 때문입니다. 하지만 이는 edge의 길이가 음수 일때는 성립하지 않습니다.

위 그림을 보면, 가장 짧은 경로는 더 멀리 지나갈 수 있다는 사실을 보여줍니다.

• S에서 A까지의 최단 경로는 더 멀리 있는 노드 B를 통과해야 합니다.

이 문제를 해결하기 위해 Dijkstra’s algorithm에 대한 high-level의 관점을 살펴보겠습니다.
crucial invariant: dist값은 항상 과대평가되거나 정확합니다.

• 시작은 $∞$에서 시작합니다.
• 거리값이 바뀔 때는 오직 edge를 따라 업데이트하는 방법 밖에 없습니다.(아래의 사진 참조)
• 

이 update 함수는 u까지의 거리는 u까지 거리와 $l(u, v)$를 더한 값보다 더 클 가능성이 없다는 간단한 사실을 이용한 것입니다.

그리고 update는 다음과 같은 2가지 특성이 있습니다.
1) 아래의 경우에 v까지 정확한 거리를 줄 수 있습니다.

• v로 가는 가장 짧은 경로 속 2번째 노드가 u인 경우
• dist(u)가 정확한 경우 2) dist(v)를 너무 작게 만들지 못한다는 관점에서, safe하다고 말할 수 있습니다.
• 즉, 엄청 많은 수의 update문에 영향을 받지 못합니다.
• (해가 되는 연산이 아니고, 적절한 상황에서 잘 사용한다면 올바른 거리 값을 구할 수 있다는 뜻입니다.)

그리고 사실 다익스트라의 알고리즘은 update를 단순히 나열한 것으로도 볼 수 있습니다만, 단순한 나열이 negative edges에선 동작하지 않습니다.

하지만 가능하게 하는 특정 시퀀스가 존재한다면 어떻게 될까요?

• 노드 t를 하나 고르고, s에서 출발하는 가장 짧은 경로를 확인합니다.
• 이 경로는 최대 $\vert V \vert -1$ edges를 가집니다.
• 만약 경로에 존재하는 edge들이 최단 경로 방향 순으로 잘 update가 되었다고 한다면, t는 올바르게 계산될 것입니다.
• 이 엣지들에 다른 update가 발생해도 크게 문제는 없습니다. 추가적으로 다른 부분에 업데이트가 발생해도 문제는 없습니다.
  • update가 safe하다는 특성 때문입니다.
• 그래도 여전히 문제는 남습니다. 올바른 순서대로 올바르게 업데이트할 수 있을지에 대한 보장이 없습니다.
• 단순하게 모든 edge들에 대해 $\vert V \vert -1$번 업데이트를 하겠습니다.
• 이렇게 될 경우, 시간 복잡도는 $O(\vert V \vert \cdot \vert E \vert)$ 입니다.
• 이를 Bellman-Ford algorithm이라고 합니다. 아래의 두 장의 사진을 참고하면 됩니다.

어떤 정점으로부터 최소 경로의 최대 엣지 갯수는 V-1이니까, 그거보다 작을 떄가 더 많았습니다. 따라서, sp 알고리즘에 extra 작업을 체크해주는 작업을 해줘야 합니다.

• 더이상의 업데이트가 일어나지 않는 경우 terminate 해줍니다.

4.6.2 Negative cycles

그래프에 Negative cycles이 존재할 경우, 계속 반복해서 경로의 길이 값을 낮출 수 있습니다. (= ill-posed)
기존의 SP 알고리즘은 이러한 사이클이 없는 경우에만 동작합니다. 그럼 이러한 가정이 어디서 왔을까요?
바로 s에서 t로 가는 가장 짧은 경로의 존재성에 대해 언급했을 떄입니다. 이 negative cycle을 검출하는 방법을 생각할 수 있습니다.

• $\vert V \vert -1$번의 루프를 수행하고 나서, 추가적으로 한 번더 루프를 돌릴 수 있습니다.
• 이 루프를 돌렸을 때, 거리값의 변화가 있다면 negative cycle이 존재한다고 볼 수 있습니다.

Reference

1. Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani(http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf)
2. https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/