[알고리즘] C++로 벨만-포드 알고리즘 구현하기

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

그래프에서 최단 경로를 찾는 알고리즘은 여러 개가 있기 때문에, 알고리즘이 필요할 때에는 각 상황에 맞는 적절한

최단경로 알고리즘을 선택해야한다. 널리 사용되는 최단경로 알고리즘으로는

다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘이 있다.

특히, 다익스트라 알고리즘과 벨만-포드 알고리즘은 굉장히 많이 쓰이기 때문에, 다음과 같이 비교하면 좋다.

• 벨만-포드 알고리즘은 간선 간의 가중치가 음수일 때 사용한다. 다익스트라 알고리즘은 양수 가중치만 가능하다.
• 다익스트라 알고리즘은 정점을 기준으로 최단 경로는 찾고, 벨만-포드 알고리즘은 간선을 기준으로 찾는다.

 

2. 벨만-포드 알고리즘의 조건

벨만-포드 알고리즘을 적용하기 위한 조건은 다음과 같다.

• 최단 경로는 출발점으로부터 도달가능하며, 음의 값을 가지는 순환이 없는 경우로 생각할 수 있다.
• 최단 경로는 순환을 포함해서는 안 된다.
• 최단 경로의 길이는 최대 |V| - 1 이다.

 

3. 벨만-포드 알고리즘의 구현

#include <iostream>
#include <vector>
#include <algorithm>

#define INF 214700000

using namespace std;

typedef pair<int, int> P;
int V, E, K;

vector<vector<P>> graph;

vector<int> bellman_ford()
{
	vector<int> d(V, INF);
	d[K - 1] = 0;

	for (int i = 0; i < V - 1; i++)
	{
		for (int j = 0; j < V; j++)
		{
			for (int k = 0; k < graph[j].size(); k++)
			{
				if (graph[j][k].first + d[j] < d[graph[j][k].second])
				{
					d[graph[j][k].second] = graph[j][k].first + d[j];
				}
			}
		}
	}

	int dSum = 0;
	for (int i = 0; i < d.size(); i++) dSum += d[i];
	vector<int> dCopied(d);

	for (int j = 0; j < V; j++)
	{
		for (int k = 0; k < graph[j].size(); k++)
		{
			if (graph[j][k].first + dCopied[j] < dCopied[graph[j][k].second])
			{
				dCopied[graph[j][k].second] = graph[j][k].first + dCopied[j];
			}
		}
	}
	int dCopiedSum = 0;
	for (int i = 0; i < dCopied.size(); i++) dCopiedSum += dCopied[i];

	if (dSum != dCopiedSum)
	{
		// There is a negative loop.
	}

	return d;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> V >> E;
	cin >> K;
	graph.assign(V, vector<P>());

	while (E--)
	{
		int u, v, w;
		cin >> u >> v >> w;

		graph[u - 1].push_back(P(w, v - 1));
	}

	vector<int> d = bellman_ford();
	for (int i = 0; i < d.size(); i++)
	{
		if (d[i] == INF) cout << "INF" << '\n';
		else cout << d[i] << '\n';
	}

	return 0;
}