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

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

벨만-포드 알고리즘은 가중치 방량 그래프에서 최단 경로 문제를 푸는 알고리즘입니다. 다익스트라 알고리즘에서 간선의 가중치가 음수일 수 없었던 것에 반해 벨만-포드 알고리즘은 가중치를 음수 값으로 갖는 것이 가능합니다. 다만 속도 측면에서 다익스트라 알고리즘이 벨만-포트 알고리즘에 비해 빠른 속도를 갖습니다.

 

과정은 어떤 한 정점에서 어떤 다른 정점으로 갈 때 그 정점의 개수가 N개면 최대 N-1개의 간선을 사용해야 합니다. 그렇게 시장 정점에서 각 정점까지 가는 가는 최소 가중치합을 간선의 선택개수를 N - 1개까지 증가시키며 비교해주면 됩니다. 그렇게 최소 값들을 유지시키면 됩니다.

마지막으로 N - 1 번째 시행했을 때 남은 값들을 출력합니다.

 

예시 코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define INF 100000000

int N, M;
int dist[101];
bool cycle;//음의 사이클을 갖는지 확인
vector<pair<int, int>> v[101];

void BellmanFord() {
	for (int i = 1; i <= N; i++)
		dist[i] = INF; // 모든 노드 INF 초기화

	dist[1] = 0; // 시작점 0으로 초기화

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 0; k < v[j].size(); k++) {//j노드를 기준으로 연결된 노드들 체크
				int next = v[j][k].first;
				int cost = v[j][k].second;

				if (dist[j] != INF && dist[next] > dist[j] + cost) {
					dist[next] = dist[j] + cost;
					if (i == N) cycle = true;//N-1까지 확인한 이후에도 갱신이 된다면 음의 사이클이 존재
				}

			}
		}
	}

	if (cycle) cout << -1 << '\n';
	else {
		for (int i = 2; i <= N; i++)
			cout << (dist[i] != INF ? dist[i] : -1) << '\n';
	}
}