Solving System of Difference Constraints

http://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/

30분 정도부터 보면 된다.

간략히 말하자면 변수 x1 ... xn N개와, xj - xi <= T 꼴의 부등식 M개가 있을 때, 이를 만족하는 변수 {x1 ... xn} 를 O(NM)에 벨만 포드로 찾을 수 있다는 것이다. 부등식의 꼴이 간단하기 때문에 복잡한 선형 계획법 알고리즘을 요하지 않는다.

방법은, xj - xi <= T일때, i -> j로 가는 가중치 T의 간선을 만들어주는 것이다. 이러한 일련의 작업이 끝났다면, 임의의 정점 i에서 벨만 포드를 돌렸을 때, xj = xi + ShortestPath(i, j) 라는 값을 대입했을 때 저것을 만족함을 보장할 수 있다. 

증명은,

* 1. 음수 사이클이 있으면 식을 만족하는 해가 없다 : 임의의 사이클에 대응되는 부등식을 모두 더해주면, 0 <= 사이클의 가중치 합 이라는 식으로 변형된다는 것을 알 수 있다. 이가 0보다 작으면 모순.

* 2. 음수 사이클이 없으면 저 답은 항상 해가 된다 : 부등식 xa - xb <= T를 보자. 이에 우리가 구한 값을 대입하면 ShortestPath(i, a) - ShortestPath(i, b) <= Weight(b, a) 라는 식이 나온다. ShortestPath(i, a) <= ShortestPath(i, b) + Weight(b, a)인데, 이는 유명한 삼각 부등식이고 최단 경로라는 조건 덕에 항상 만족한다.

연습 문제 : https://www.acmicpc.net/problem/7577