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

Bellman-ford

• 노드에서 노드까지의 최소 비용을 구함
• 매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용을 갱신하므로 음의 가중치를 가지는 그래프에서도 최단 경로를 구할 수 있음

1. 시작 노드를 설정한 다음 시작 노드의 최소 비용은 0, 나머지 노드는 INF로 초기화. 이후 최소 비용을 갱신할 때 직전 노드도 갱신
2. 노드 개수 -1만큼 다음 연산을 반복
   2-1. 시작 노드에서 갈 수 있는 각 노드에 대하여 전체 노드 각각을 거쳐갈 때 현재까지 구한 최소 비용보다 더 적은 최소 비용이 있는지 확인하여 갱신. 최소 비용을 갱신할 때, V의 직전 노드 값도 같이 생신
3. 과정 2를 마지막으로 수행하여 갱신되는 최소 비용이 있는지 확인(만약 있다면 음의 순환이 있음을 의미)

정점 개수 -1마다 반복하는 이유

• 매 연산마다 최단 경로가 1개씩 확정되기 때문
  
  출처 : 코딩테스트 합격자되기 자바편

한 번 더 연산을 반복하는 이유

• 음의 순환을 찾기 위해

음의 순환에 빠지는 것은 벨만 포드 알고리즘의 한계다?

• 아님. 그래프에 음의 순환이 잇으면 그 어떤 알고리즘도 최단 경로를 구할 수 없음
• 오히려 음의 순환을 감지해서 더 좋음