벨만-포드(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;
}
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
최소 비용 신장 트리 - 크루스칼(Kruskal) 알고리즘. (0) | 2020.11.23 |
---|---|
최단 경로 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘 (0) | 2020.11.23 |
최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra) (0) | 2020.07.16 |
탐색 알고리즘 - 너비 우선 탐색(Breadth First Search, BFS) (0) | 2020.06.22 |
탐색 알고리즘 - 깊이 우선 탐색(Depth First Search, DFS) (0) | 2020.06.22 |
댓글