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

💡 벨만-포드(Bellman-Ford) 알고리즘이란?

벨만-포드

• 한 노드에서 다른 모든 노드까지 최단 거리를 구하는 알고리즘
• 매 단계마다 모든 간선을 전부 확인하면서 모든 노드 간의 최단 거리를 구함
  • 다익스트라는 방문하지 않은 노드 중 최단 거리가 가장 가까운 노드를 방문함
• 간선 가중치가 음수일 때도 최단 거리를 구할 수 있음
• 시간 복잡도: O($VE$)

알고리즘 구현 방식

• 아래 과정을 V-1 번 반복
  • 모든 간선 E개에 대해 각 간선을 거쳐 다른 노드로 가는 비용을 계산 후 최단 거리 테이블 갱신
  • 음수 사이클이 존재하는지 체크하고 싶다면 과정을 한번 더 수행
  • → 이 때 최단 거리 테이블이 변화가 있다면 음수 간선 순환 존재

1. 초기 상태

 

A	B	C	D	E
INF	INF	INF	INF	INF

 

 

 

 

 

2. 모든 edge 탐색하여 노드 최솟값 업데이트

 

- A out 간선 탐색하여 주변 노드 업데이트

A	B	C	D	E
0	-1	4	INF	INF

 

 

 

 

- B out 간선 탐색하여 주변 노드 업데이트

A	B	C	D	E
0	-1	2	0	1

 

 

 

 

 

- C out 간선 탐색하여 주변 노드 업데이트

A	B	C	D	E
0	-1	2	0	1

 

 

 

 

 

- D out 간선 탐색하여 주변 노드 업데이트

A	B	C	D	E
0	-1	2	0	1

 

 

 

- E out 간선 탐색하여 주변 노드 업데이트

A	B	C	D	E
0	-1	2	0	1

 

 

 

 

- 첫 번째 사이클 완료

A	B	C	D	E
0	-1	2	0	1

 

 

 

 

- 이런 과정의 탐색을 V-1번 진행

- 순서는 꼭 노드 순서대로 A, B, C, D, E가 아니어도 된다. 모든 edge를 탐색하는 것이 중요!!!