벨만 포드 알고리즘 (Bellman-Ford algorithm)

벨만 포드 알고리즘(Bellman-Ford algorithm)은 다익스트라 알고리즘과 마찬가지로 하나의 정점에 대한 모든 정점의 최단 거리를 찾는 문제에 적용됩니다. 다익스트라는 음수간선이 존재하면 사용할 수 없지만 벨만 포드 알고리즘은 음수간선이 존재해도 사용할 수 있습니다. 가중치의 합이 0보다 작은 싸이클을 음수 싸이클이라고 하는데, 그래프에 음수 싸이클이 존재하면 벨만 포드 알고리즘을 사용할 수 없습니다. 다음은 벨만 포드 알고리즘이 적용되는 문제입니다. https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의..

2020.03.25