[백준][BOJ11657] 타임머신

1. 문제 : https://www.acmicpc.net/problem/11657

11657번: 타임머신

---

2. 풀이 : Bellman-Ford

---

3. 시간복잡도 : O(VE)

---

4. 설명

Bellman-Ford 알고리즘은 'V-1'회의 edge relaxation 수행으로 한 노드로부터 다른 노드까지의 최단 경로를 구할 수 있다.

그림[1]

그림[1]에서 1번 도시로부터 다른 모든 도시까지의 최단 경로를 구해보자. edge relaxation을 'V-1'회(2회)를 수행한 결과는 그림[2]와 같으며, edge relaxation을 추가 1회 수행하여도 결과는 같음을 알 수 있다. 따라서, 2번 도시까지의 최단 경로의 시간은 4이며, 3번 도시까지의 최단 경로의 시간은 3이다.

그림[2]

그림[3]은 edge relaxation을 'V-1'회 수행하여 1번 도시로부터 다른 모든 도시까지의 경로를 구한 또 다른 예시이다.

그림[3]

3번 도시로 가는 경로는 존재하지 않기 때문에 초기값인 INF에서 변함이 없음을 확인할 수 있다. 그림[3]의 예제 역시 edge relaxation을 추가 1회 수행하여도 최단 경로의 값은 변함이 없다. 따라서, 2번 도시까지의 최단 경로 시간은 3이며, 3번 도시까지의 최단 경로는 존재하지 않는다.

그림[4]는 edge relaxation을 'V-1'회 수행하여 1번 도시로부터 다른 모든 도시까지의 경로를 구한 또 다른 예시이다.

그림[4]

그림[4]에서 edge relaxation을 추가 1회 수행하면 그림[5]와 같다.

그림[5]

그림[5]와 같이 edge relaxation 추가 1회 수행으로 최단 경로의 값이 변하는 것을 알 수 있다. 따라서, 위의 예시는 음수 싸이클이 존재한다.

---

5. 코드