최단 경로. [11657]

[1. 문제 설명]

그래프 내 음수 가중치가 있을 때, 

1번 정점에서 각 정점으로의 최단 경로를 출력

 

음수 사이클이 발생하는 경우는 -1 하나만 출력

특정 노드를 도달 할 수 없는 경우에 -1 출력 

 

 

 

[2. 풀이 접근]

edge 에 음수 가중치가 있는 경우는 다익스트라 알고리즘을 이용하여

최단 경로를 구할 수는 없다.

다익스트라 알고리즘은 정점을 지날 수록 경로의 가중치가 커지는 것을 기반으로 하기 때문이다.

(정점을 여러 개 지났는데, 오히려 가중치가 작아지는 경우...)

 

이 경우, 벨만포드 알고리즘을 이용하여 최단 경로를 계산하는데,

여기서 중요한 것은 음수 사이클이 발생하는 것을 판단하는 것이다.

 

A -> B -> C 로 갈 때, A -> B 의 weight 가 +2 이고, B -> A 의 weight -3 이면,

A <-> B 를 반복하면, weight 가 계속 작아지는 것을 생각해 볼 수 있다.

 

벨만포드 알고리즘의 pesudo code 는 아래와 같다.

~~~

 

~~~

 

여기서 한가지 간과할 수 있는 부분은 다음과 같다.

from -> to 에서 from 이 반드시 먼저 방문되었음이 보장되지 않는다.

 

벨만포드는 

bfs 나 dijkstra 처럼 어떤 정점을 먼저 방문하고, 인접 정점을 방문하는 것이 아니고,

edge 단위로 순회하기 때문에 from 이 아직 방문되지 않았을 수 있다.

 

여기서, weight 계산에서 오버플로우가 발생하여 오동작 할 수 있다.

 

 

[3. 코드]