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

최단 경로 탐색 알고리즘.

 

간선 가중치가 음수인 경우에도 적용가능함.

 

단, 사이클의 가중치 합이 음수인 경우가 존재하는 그래프는 최단 경로를 구할 수 없음. 

 

 

1. 그래프의 간선정보를 저장. (출발노드, 도착노드, 가중치) 를 저장.

2. 시작 노드를 지정.

3. 모든 정점까지의 거리를 무한대로 설정.

4. 모든 간선을 확인해, 출발노드에서 도착노드로 이동했을때의 거리가 이미 저장된 도착노드까지의 거리보다 짧은경우 거리를 갱신. 거리 = 가중치. dist[v] > dist[u] + w 인 경우, dist[v] = dist[u] + w 로 갱신.   

5. 4를 V-1번 반복. V는 노드 수.

6. 음수 사이클여부를 확인하려면 한번더 반복하고, 이때 거리가 갱신되는 노드가 발견되면 음수사이클이 존재함.