[그래프 알고리즘]벨만포드 알고리즘

음수 가중치

벨만포드 알고리즘은 음수 가중치가 존재 할수도 있는 그래프에서 한 노드로부터 다른 노드들로의 최단 거리를 구하는 알고리즘 입니다.

음수 가중치 사이클이 존재하는 경우 이를 확인하는 것도 가능합니다.

음수 가중치 사이클이란 한 사이클을 순회할 때 가중치의 합이 계속 작아지는 사이클을 말합니다.

Relaxation

시작 노드에서 다른 노드까지의 최단 거리를 나타내는 리스트 dist가 있다고 합시다.

그리고 노드 u에서 노드 v로 가는 가중치 w인 엣지가 있다고 할 때,

dist[v]가 dist[u] + w보다 크다면, dist[v]를 dist[u] + w로 업데이트 될 수 있습니다.

이를 모든 엣지에 대해 적용하는 것이 1번의 relaxation입니다.

relaxation을 적용하면, 시작노드로부터 주변 노드로의 최단 거리값이 갱신됩니다.

이를 반복하면 결국 모든 노드로의 최단 거리를 구할 수 있습니다.

 

그러면 이 relaxation을 몇번 해야할까요?

노드의 개수가 N개인 그래프에서 모든 노드가 일렬로 연결되어 있는 경우, 첫번째 노드로부터 마지막 노드까지 N-1개의 엣지가 있으므로,

최대 N-1번 relaxation을 반복하면 시작노드로부터 모든 노드로의 최단 거리를 구할 수 있습니다.

최대 N-1번이므로 그보다 적은 반복에서 최단거리가 갱신되지 않으면 반복을 중단해도 됩니다.

 

음수 가중치 사이클이 없다면, N-1번째 이후의 relaxation에서는 최단거리가 갱신되지 않아야 합니다.

따라서 N번째 relaxation에서 최단거리가 갱신된다면 음수 가중치 사이클이 있음을 알 수 있습니다.

구현