[자료구조/알고리즘] 벨만-포드(Bellman-Ford) 알고리즘

다익스트라, 플로이드-와샬과 함께 노드와 간선, 간선의 비용이 주어진 상황에서 최단 거리를 구할 수 있는 알고리즘 중 하나이다. 다익스트라와 작동 방법이 유사하지만, 존재하는 모든 간선에 대해 최단 거리를 업데이트하는 시행을 (노드의 개수 -1)만큼 진행하는 것이 그 특징이다. 또한 노드의 개수만큼 업데이트한다면 경로 내에 음수 간선의 순환이 있는지 여부도 파악할 수 있다.

 

[동작 과정]

① 출발 노드 설정 및 최단 거리 테이블 초기화(충분히 큰 숫자로, 시작 노드는 0으로 초기화)

② 아래의 과정을 N-1번 반복

    ②-1: 전체 간선 E개에 대하여 확인

    ②-2: 해당 간선을 이용해 이동하는 것이 더 짧은 경로라면, 이를 이용해 최단 거리 테이블 갱신

③ ②의 과정을 한 번 더 수행하여, 이때 최단거리 테이블이 업데이트 된다면 음수 간선의 순환이 있다고 판단할 수 있다.(N개의 노드를 거쳐 이동할 때 음수 간선의 순환이 없다면 최대 N-1개의 간선 내에 최단거리가 나와야 하는데, N번째 시행에도 최단거리 테이블이 업데이트 된다는 것은 음수 간선 순환이 존재함을 의미한다.)

 

구현 예시, 문제 풀이: https://mingchin.tistory.com/310

[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1865번 _ 웜홀

코드에서 알 수 있듯 다익스트라와 비슷하게 한 노드에서 다른 모든 노드까지의 거리를 업데이트 해나가며, 노드의 방문 여부 확인을 해당 노드까지의 거리가 INF인지 아닌지를 확인하는 것으로 대체한다.

 

노드의 개수 N, 간선의 개수 E에 대하여 O(N*E)의 시간복잡도를 가진다.