[Algorithm] 벨만-포드(bellman-ford-moore)

벨만-포드

• 벨만-포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 다음과 같은 특징이 있습니다.

기능	특징	시간 복잡도
특정 출발 노드에서 다른 모든 노드까지의 최단 경로 검색	- 음수 가중치가 있어도 수행 가능 - 전체 그패스에서 음수 사이클의 존재 여부를 판단 가능	O(VE)

벨만-포드의 원리

1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화하기

• 에지 리스트는 출발 노드, 도착 노드, 가중치 3개의 정보를 가지고 있습니다.
• 최단 경로 배열은 출발 노드는 0 나머지는 INT_MAX로 초기화합니다.

2. 모든 에지를 확인하며 정답 배열 업데이트 하기

• 최단 경로 배열의 업데이트 횟수는 노드 개수 -1개입니다.
• 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수가 N-1개이기 때문입니다.
• 업데이트 횟수가 K번이라면 최단 경로 배열은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리입니다.

업데이트 조건

if(dist[now] != INT_MAX && dist[next] > dist[now] + weight)
	dist[next] = dist[now] + weight;

3. 음수 사이클 유무 확인하기

• 음수 사이클을 확인하기 위해선 모든 에지를 다시 사용해 업데이트 합니다.
• 만약 업데이트되는 노드가 있다면 음수 사이클이 발생한다는 뜻입니다.
• 음수 사이클이 존재하면 최단 경로를 찾을 수 없는 그래프입니다.