image.png

벨만 포드 알고리즘이란

한 정점을 기준으로 다른 정점과의 최단 거리를 찾아주는 알고리즘이다. 다익스트라 알고리즘과의 차이는 다익스트라 알고리즘의 경우 음수 사이클이 존재하는 경우 제 기능을 하지 못한다. 그러나 벨만 포드 알고리즘의 경우 음수 사이클을 감지해낼 수 있다.

벨만 포드 알고리즘의 구현

벨만 포드 알고리즘은 순회와 완화 과정으로 이루어 진다. 순회는 매 정점을 확인하면서 그 정점과 연결된 간선들을 모두 확인하는 것이다. 이 때 완화 과정이 이루어 지는데, 만약 확인한 간선을 통해 생기는 경로가 현재 저장된 최단 경로보다 짧다면 최단 경로를 업데이트 하는 것이다. 이러한 확인과 업데이트 과정은 다익스트라 알고리즘을 비롯한 최단 거리 알고리즘의 공통 사항이다. 각 정점을 마지막으로 완화시킨 간선들을 모으면 최단 경로를 갖는 스패닝 트리를 얻을 수 있다.

음수 사이클의 확인

벨만 포드 알고리즘은 최대 V-1번의 순회를 한다. 스패닝 트리를 만드는 데 최대 V-1개의 간선이면 충분하기 때문이다. 이 때 V번의 순회에서 완화가 발생한다면 음수 사이클이 존재하는 것이다. 음수 사이클이 존재하지 않는 경우는 반드시 V-1번 이전에 순회가 끝나기 때문이다.

완화가 끝까지 진행된 경우 더 이상 업데이트할 최단 거리가 없어야 하지만 음수 사이클이 존재하는 경우 경로를 추가할 때마다 끝없이 최단 경로를 업데이트할 수 있으므로 V-1번을 넘어서 까지 완화 과정이 발생하는 것이다.

V번째 순회에서도 완화가 발생했다면 빈 배열을 반환해 음수 사이클의 존재를 알릴 수 있다.

시간 복잡도

벨만 포드 알고리즘은 매 순회마다 모든 간선을 확인하고 총 V번의 순회를 하므로 V*E의 시간 복잡도를 갖는다.

주의점

벨만 포드 알고리즘을 실행한 뒤 방문할 수 없는 정점을 확인할 때 최단 거리가 초기값인 무한대임을 기준으로 확인하면 안된다. 만약 해당 정점이 음수 가중치를 갖고 있는 경우 무한대보다 작은 값을 갖을 수 도 있기 때문이다. 따라서 무한대보다 가중치의 한계만큼 작은 값을 선택해서 그 값보다 큰 경우 방문할 수 없다고 판정하는 것이 좋다.