후... 넘 어려워서 나중에 다시 봐야할 듯.

boj.kr/7577

https://blog.naver.com/3587jjh/222030088627

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-18-shortest-paths-ii-bellman-ford-linear-programming-difference-constraints/lec18.pdf

https://koosaga.com/72

https://medium.com/hackernoon/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869

Bellman - Ford Algorithm

기능

음수 간선이 있는 그래프에서 $\mathcal O(|V||E|)$에 SSSP를 구할 수 있다.

음수 사이클을 감지할 수도 있다. 참고로, 음수 사이클이 존재하는 그래프에서 최단경로는 $-\infin$가 되므로 일반적으로 정의하지 않는다.

코드

vector<tuple<int,int,int>> edge;
bool hasNegativeCycle;

void bellmanFord(int x) {
  dist[x] = 0;
  for (i = 1; i < n; ++i)
    for (auto [a,b,w] : edge)
      dist[b] = min(dist[b],dist[a]+w);
  for (auto [a,b,w] : edge)
    if (dist[b] < dist[a]+w)
      hasNegativeCycle = true;
}

pseudo code만큼 그 의미를 잘 살린 코드이므로 굳이 pseudo code를 작성하지는 않았다.

정당성

$\delta(s,v)$를 $s$에서 $v$까지의 최단경로의 길이라고 정의하자. 이런 이유는 중간 프로세스에서 $\text{dist}$가 최단경로가 아닌 경우도 있기 때문이다.

Theorem. 음수 사이클이 없다면, $\mathrm{dist}[v]=\delta (s,v)$가 된다.

Proof. 최단경로 $p$를 생각하자. $p$의 시작점부터 끝점까지 방문 순서에 따라 정점들에 순서를 매길 수 있다. $p$위의 $v_1,v_2,\cdots ,v_n$에 대해 $\delta(s,v_i)=\delta(s,v_{i-1})+w(v_{i-1},v_i)$가 만족한다. 물론 $s=v_0$, $\delta(s,v_0)=0$이다.

알고리즘을 적용하여 귀납적으로 증명하자.

a. $\text{dist}[v_0]=0$, $\text{dist}[v_0]=\delta(s,v_0)$가 만족한다.

b. $k=x$일 때, $\text{dist}[v_x] = \delta(s,v_x)$이라 가정하자.

c. $k=x+1$일 때, $\text{dist}[v_{x+1}]=\text{dist}[v_{x}](=\delta(s,v_x))+w(v_x,v_{x+1}).$

$\because \text{dist}[v]\ge \delta(s,v),$ 만약 $\text{dist}[v]=\delta(s,v)$이면 갱신하지는 못해도 만족한다.

$\therefore \text{dist}[v_{x+1}]=\delta(s,v_{x+1}).$

보충 설명 : $p$ 위에서 양의 사이클은 존재할 수 없다. $\because \delta(s,v_i)=\delta(s,v_{i-1})+w(v_{i-1},v_i)< \delta(s,v_{i-1})+W.$ 0의 사이클은 생략 가능하다. 0의 사이클만을 도려낸 경로도 최단경로이기 때문이다.

따라서 $|V|-1$번의 프로세스 후 $\forall v\in V, \text{dist}[v]=\delta(s,v)$가 만족한다.

시점 $T$에 음수 사이클 위의 한 정점 $v_0$에 대해 $\text{dist}[v_0]$가 갱신되었다고 하자. 사이클 $c$에 정점이 $v_0\to v_1\to\cdots\to v_{n-1}\to v_0$를 이룬다고 하자.

시점 $T+1$에 $\text{dist}[v_1]\le\text{dist}[v_0]+w(v_0,v_1)$, 만약 $<$라면, 사이클 내부에서 갱신되고 있는 것이다.

시점 $T+n$에 $\text{dist}[v_0]\le \text{dist}[v_{n-1}]+w(v_{n-1},v_0)$로 갱신된다. 이 때도 $<$라면 갱신되고 있는 것이다.

따라서 음수 사이클이 존재하면 쉬지않고 갱신이 이뤄진다.

Solving a system of difference constraints

$x_j-x_i\le w_{ij}$형태의 부등식들을 $v_i\overset{w_{ij}}\to v_j$ 형태의 그래프로 모델링 할 수 있다.

Theorem. 그래프가 음수 사이클을 지녔다면 system이 불능이다.

Proof. 음수 사이클을 지녔다고 가정하자. $v_1\to v_2\to \cdots \to v_k\to v_1$이라면

$0\le \sum w_{ij}<0$이므로 모순이다.

Theorem. 그래프에 음수 사이클이 없다면 system이 성립한다.

Proof. Claim. 최단경로가 존재한다면 system이 성립한다.

$x_i=\delta(s,v_i)$라 하자. 삼각 부등식에 따라 $\delta(s,v_j)\le \delta(s,v_i)+w_{ij}.$

따라서 $x_j-x_i\le w_{ij}$를 잘 나타낸다.