[알고리즘] 벨만포드 (특징, 시간복잡도, 구현 방법)

특징

1. 음의 가중치를 갖는 그래프에서 최단경로를 구할 수 있다.

2. 음의 가중치 여부를 알 수 있다

 

구현 방법

모든 노드의 숫자만큼 거리가 업데이트 될 수 있는가 검사한다

V만큼 E가 업데이트 될 수 있는지 검사한다

그리고 마지막 V+1번 검사할때, 거리가 업데이트된다면 음의 가중치를 갖는 그래프이다

 

시간 복잡도

V만큼 E가 업데이트 될 수 있는지 검사하므로

O(VE)이다