벨만-포드 알고리즘(최단 경로)

🟩 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘

간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다.

 

🌟 다익스트라 vs 벨만-포드

 

1번 노드에서 3번 노드로 가는 최단 거리를 구한다고 할 때,

경로1. 1번 👉 3번 (비용 : 10) 👉 다익스트라 알고리즘

경로2. 1번 👉 2번 👉 3번 (비용 : 5) 👉 벨만-포드 알고리즘

 

✏️ 다익스트라 알고리즘

매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다.

음수 간선이 없다면 최적의 해를 구할 수 있다.

시간 복잡도가 빠르다 (O ElogV)

 

✏️ 벨만-포드 알고리즘

(정점-1)번의 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다.

cf. 다익스트라와의 차이점은 매 반복마다 모든 간선을 확인한다는 것. 다익스트라는 방문하지 않은 노드 중에서 최단 거리가 가장 가까운 노드만을 방문한다.

👉 다익스트라 알고리즘에서의 최적의 해를 항상 포함하게 된다.

음수 간선이 있어도 최적의 해를 찾을 수 있다.

시간 복잡도가 느리다. O(VE)

 

👉 모든 간선의 비용이 양수일 때는 다익스트라, 음수 간선이 포함되어 있으면 벨만-포드 사용

 

🟩 벨만-포드 구현과정

1. 출발 노드를  설정한다.

2. 최단 거리 테이블을 초기화한다.

3. 다음의 과정을 V(정점)-1번 반복한다.

    a. 모든 간선 E개를 하나씩 확인한다.

    b. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

 

만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번 과정을 한 번 더 수행한다.

👉 이 때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것

 

V번째 단계에서 최단 거리 테이블의 갱신여부로 음수 간선 순환을 확인 가능하다.

 

🟩 시간복잡도

O(VE)

V번 반복에 대해서 해당 정점과 연결되어 있는 모든 간선(E)를 탐색해주기 때문에 시간 복잡도는 O(VE)이다.