Bellman-Ford algorithm

그래프에서 특정 출발 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다.

음수 가중치가 있어도 수행할 수 있다.

전체 그래프에서 음수 사이클이 존재하는 지 여부를 판단할 수 있다.

시간복잡도는 O(VE)다.

🔰구현

1. 엣지 리스트로 그래프를 구현하고, 최단 경로 리스트를 초기화한다. 최단 경로 리스트의 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.
2. 모든 엣지를 확인해 최단 거리 리스트를 갱신한다. 이 갱신 반복 횟수는 (그래프의 노드 개수 - 1)번이다. 사이클이 없는 그래프에서 특정 두 노드의 최단 거리를 구성하는 엣지의 최대 개수는 (전체 노드 개수 - 1)이기 때문이다. 엣지 리스트에서 선택한 엣지의 출발 노드의 최단 거리 배열의 값이 무한대가 아닐 때, 도착 노드의 최단 거리 배열의 값을 min(출발 노드의 최단 거리 배열의 값 + 현재 엣지의 가중치, 도착 노드의 최단 거리 배열의 값)로 갱신한다.
   • 갱신 반복 횟수(K)는 해당 시점의 최단 거리 리스트의 값이 K개의 엣지를 사용했을 때 각 노드에 대한 최단 거리라는 것을 의미한다.
   • 음수 사이클이 없을 때 (그래프의 노드 개수 - 1)번을 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려 주는 최단 거리 리스트가 완성된다. 
3. 완성 후, 음수 사이클이 존재하는 지 확인해야 한다. 모든 엣지를 한 번씩 다시 사용해서(한 번 더 갱신 시도) 갱신되는 노드가 있는지 확인한다. 만약 있다면, 음수 사이클이 있다는 뜻이고 최단 거리를 찾을 수 없는 그래프라는 뜻이다. 음수 사이클이 존재하면 사이클을 무한히 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없다.