최단 거리 알고리즘 - 벨만-포드(Bellman-Ford) 알고리즘

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

 

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

 

 - 모든 정점으로 가는 최단 거리를 찾는 알고리즘.

 

 - 하나의 정점에서 출발하여 모든 정점으로 가는 최단 거리를 알 수 있다.

 

 - 음수의 가중치가 있는 경우에도 최단 경로를 찾을 수 있다. 

 

 - 음의 사이클이 발생한 경우를 판별할 수 있다.

 

 - 최단 경로는 각 정점을 한 번씩만 지나기 떄문에, 최단 경로의 간선 개수는 V-1개 이다.

   (같은 정점을 지날 때 거리가 줄어든다면, 음의 사이클이 발생한 경우이다.)

 

 - 출발 정점에서 1개 ~ V-1개의 간선을 지나서 도착하는 경우를 모두 살펴보고, 그 중 최소 값을 찾아내는 방법이다.

 

 - 시간 복잡도는 O(VE)이다. (V은 정점의 개수, E은 간선의 개수)

 

 

---

 

벨만-포드 알고리즘 실행 과정

 - 1. 출발 정점과 나머지 정점들까지의 거리를 무한대로 설정한다.(출발 정점에서 출발 정점까지의 거리는 0)

 

 - 2. 모든 간선들을 살펴보며 거리 값을 갱신할 수 있는 경우 갱신한다. 

      현재 정점의 거리 + 연결된 정점까지의 가중치 > 연결된 정점의 거리 인 경우 연결된 정점의 거리 값을 갱신한다.

      ( distance[i] + weight[i][j] > distance[j] )

 

 - 3. 2번의 과정을 통해 거리 값을 더이상 줄일 수 없을때 까지 반복한다.

 

 - 4. 2~3번 과정을 V-1번 반복한다.

 

 - 5. 4번까지 모두 마친 후, 모든 간선을 다시 탐색하여, 거리값이 줄어들면 음의 간선이 있다고 판단한다.

 

  

- 초기 상태

- 1과 연결된 간선들을 탐색하여 2와 3의 거리 값을 갱신했다.

- 2와 연결된 간선을 이용하여 4를 갱신. 3과 연결된 간선을 이용했지만, 기존의 거리 값이 더 작기 때문에 갱신되지 않았다.

- 4와 연결된 간선을 탐색했지만, 기존의 거리 값이 더 작기 때문에 갱신되지 않았다.

 

- 위 과정을 V-1번인 3번 반복한 결과이다.

 

---

 

벨만 포드 코드(C++)

#include <bits/stdc++.h>

using namespace std;

void bellman_ford(vector<vector<pair<int,int>>> edge,int start)
{
	vector<int> distance(edge.size(),INT_MAX);

	distance[start] = 0;

	for (int n = 0; n < edge.size() - 1; n++)
	{
		for (int i = 0; i < edge.size(); i++)
		{
			for (int j = 0; j < edge[i].size(); j++)
			{
				// 정점 i 에서 v 까지의 가중치 cost
				int v = edge[i][j].first;
				int cost = edge[i][j].second;

				// distance[i]의 값이 무한대인 경우는 판단하지 않는다.
				if (distance[i] != INT_MAX && distance[v] > distance[i] + cost)
				{
					distance[v] = distance[i] + cost;
				}
			}
		}
	}

	for (int i = 0; i < edge.size(); i++)
	{
		for (int j = 0; j < edge[i].size(); j++)
		{
			int v = edge[i][j].first;
			int cost = edge[i][j].second;

			// 거리 값이 변경되는 경우 음의 사이클이 발생한 것이다.
			if (distance[i] != INT_MAX && distance[v] > distance[i] + cost)
			{
				cout << "음의 사이클 발생\n";
				return;
			}
		}
	}

	for (int i = 0; i < distance.size(); i++)
	{
		cout << start << " 에서 " << i <<" 까지의 최단 거리 : " << distance[i] << endl;
	}

}




int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<vector<pair<int, int>>> edge;
	edge.push_back({ { 2,5 },{1,3 } });
	edge.push_back({ { 3,6 } });
	edge.push_back({ {1,6} });
	edge.push_back({ {1,-2} });

	bellman_ford(edge, 0);

	return 0;
}

실행 결과