[Algorithm] 벨만-포드 알고리즘(Bellman-Ford algorithm)

벨만-포드 알고리즘이란?

 

한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘에 비해 시간적 효율은 떨어지지만 가중치가 음수일 때 다익스트라 대신 사용한다. 

 

벨만-포드의 특징

• 하나의 시작점에서 모든 정점까지의 최단 경로를 구하는 SSP(Single Source Shortest Path) 알고리즘
• 모든 정점을 V-1번 갱신한 뒤, 한 번 더 갱신을 시도하는 브루트포스적 접근
• 정점의 수를 V, 간선의 수를 E라고 할 때, 시간 복잡도는 O(VE)