궤도

문제 풀이 보통의 최단거리는 다익스트라 알고리즘을 사용하지만 간선의 가중치가 음수인 경우 다익스트라를 무한루프에 빠질 수 있다. 어떤 경우에 그렇게 되는지는 내가 설명하긴 귀찮고 구글에 자료가 많으니 검색해보면 될 것이다. 아무튼 그럴때 쓰는 방법이 벨만-포드 알고리즘인데 정점을 기준으로 최단거리를 갱신해 나가는 다익스트라와 달리 이건 간선을 기준으로 최단거리를 갱신한다. 정점 A, B, C가 있다고 하자. 정점의 개수 V는 3이다. 아무리 멀리 돌아가도 최단경로라면 (V-1)개의 간선을 지날 것이다. A-B-C인 경우 A-C로 가는 경로에 간선이 2개 있는 것처럼 말이다. 만약 V개의 간선을 지나서 갈 수 있는 최단경로라면? 이건 음의 사이클이 발생한 것이다. 그러므로 일단 V-1번동안 간선을 살펴보며..