11657번: 타임머신 www.acmicpc.net 이 문제는 이전의 최단 경로 문제와 유사하나 경로의 가중치가 음수가 될 수 있다는 점에서 약간 차이가 있다. 하지만, 이로 인해 이 문제를 Dijkstra 알고리즘을 이용해 풀 수 없다. 왜냐하면 특정 간선들로 인해 음의 사이클(cycle), 즉 간선들을 반복적으로 지나갈 수록 경로들의 총 가중치가 지속적으로 감소하는 현상이 발생하기 때문이다. 이 때문에 Dijkstra 알고리즘에서 최단 경로를 구하려고 하면 계속 음의 사이클을 돌게 되면서 결국 최단 경로를 찾지 못하는 경우가 발생한다. 이를 방지하기 위해 Bellman-Ford 알고리즘을 이용한다. 이 알고리즘은 Dijkstra와는 달리 우선 모든 정점들에 대해 그 정점들과 인접한 점들에 relax를..
