Bellman Ford Algoritm
그래프에서 최단경로 탐색 문제에 대한 3가지 알고리즘이있다.
- Bellman-Ford Algoritm (벨만-포드 알고리즘)
- Dijkstra Algoritm (다익스트라 알고리즘)
- Floyd-Warshall Algoritm (플로이드-와셜 알고리즘)
그래프의 특성에 따라 사용하는 알고리즘이 다르다. 이 글에서는 BellmanFord 알고리즘에 대해 이야기 해 보겠다.
1. 벨만 포드 알고리즘소개
이 알고리즘은 벨만 과 포드의 알고리즘을 기반으로 만든 알고리즘 이라하여 벨만 포드 알고리즘 이라 명명되어 있다.
가중치를 갖는 유향 그래프에서 최단경로를 찾는 알고리즘이며, 보통 다익스트라 알고리즘에 비해 느린 시간복잡도 O(|E|*|V|) 갖는다.
2. 벨만 포드 알고리즘 사용 용도
그렇다면 이 알고리즘을 사용하는 용도가 무엇일까?
그 이유는, 벨만포드 알고리즘을 사용하면 간선이 음의 가중치를 가져도 최단거리를 구할 수 있다는 것이다.
벨만포드 알고리즘이 음의 가중치를 가져도 되는 이유는 벨만포드 알고리즘 동작 과정을 보면 알수있다.
3. 벨만 포드 알고리즘 동작
벨만 포드 알고리즘의 구현 방식은 간단하다.
모든 간선(Edge)을 순회 하면서, 각 각선에서 출발지점 노드(Vertex)가 MAXIMUM 값이 아니고, 간선의 가중치와 출발지점 노드 까지의 거리의 합이 원래 도착지점 노드가 가지고 있던 거리값 보다 작다면 그값을 갱신해준다.
1의 과정을 모든 정점(Vertex) 가 갱신 될 때까지 반복한다. 즉, 모든 Vertex가 더이상 Update 되지 않을 떄 까지 반복한다.
위그림을 차례대로 설명해 보겠다.
- 처음 시작점지점은 당연히 0의 값을 가지고있는다. 그다음 나머지 Vertex까지의 거리는 모두 최대한 높은 값을 가지고 있는다.(MAXIMUM VALUE, 위그림에서는 99로 표현되어 있다.)
Edge Traverse를 한번하면 , 시작지점 에서 부터 갱신 될 수 있는, 3개의 Vertex 의 거리값이 갱신된다 (7, 4 ,9) 나머지 값들은 edge의 시작지점이 아직 Maximum 값을 가지고 있기 떄문에 갱신 될수 없다.
2 번과 같은 과정을 모든 Vertex가 갱신 될떄까지 반복한다.(Update 가 더이상 없을 떄 까지)
결국 이 모든 과정을 수행하는데, 모든 엣지를 계속순회하는데 (|E|) , 시작지점을 제외한 모든 Vertex를 갱신하는데 (|V| -1) 의 시간이 걸리므로 O(|E| * |V|) 의 시간 복잡도를 갖는다.
그런데 이런 과정을 하는데 는 간선의 가중치가 음의 값을 가져도 상관 없음을 알고리즘 순서를 이해 했다면 알수있다.
모든 Edge 를 매번 순회 하기 때문에 계속 해서 갱신이 이루어 질수 있고, 떄문에 돌아서 다시 그 Vertex에 대한 값을 갱신해 줄수 있기때문에 음의 가중치를 가질수 있다.
그런데 여기서 그것 떄문에, 문제가 발생한다.
음의 가중치 때문에, 길을 돌아서 다시 그곳에 도착했을떄 원래 돌지 않았을 떄 보다 더 적은 값이 나올 수 있다.
이런경우엔 같은 길을 계속돌면 돌수록 더 적은 값이 나오게 되는데,벨만 포드 알고리즘에서는 이러한 음의 폐로(Negative Cycle)가 나오는 문제를 방지해야 한다.
4. 소스코드
아래의 소스코드를 이해하면 더욱이 벨만포드 알고리즘을 쉽게 이해할 것이다.
4-1. SearchShortestPath
struct Edge{
int from;
int to;
int cost;
};
Edge edges[50];
int d[50];
int verCnt,edgeCnt;
bool isUpdated = true;
void BellmanFord(int startPos) {
for (int i = 0; i<verCnt; i++)
d[i] = INT_MAX;
d[startPos] = 0;
while (isUpdated == true){
isUpdated = false;
for (int i = 0; i< edgeCnt; i++){
Edge e = edges[i];
if (d[e.from] != INT_MAX && d[e.to]> d[e.from] + e.cost){
d[e.to] = d[e.from] + e.cost;
isUpdated = true;
}
}
}
}
4-2 FindNegativeCycle
최단경로를 찾아 내고 다시한번더 검사했는데, 값을 다시 갱신한다면 음의 폐로(Negative Cycle)이 존재한다.
즉, V번쨰에서(마지막에서) 값을 갱신한다면 음의 폐로 가 존재함을 알수있다.
아래의 코드는 음수 사이클인지 판별 하는 코드 이다.
struct Edge{
int from;
int to;
int cost;
};
Edge edges[50];
int d[50];
int verCnt, edgeCnt;
bool isUpdated = true;
bool is_negative_cycle(int startPos) {
for (int i = 0; i<verCnt; i++)
d[i] = INT_MAX;
d[startPos] = 0;
for (int i = 0; i < verCnt;i++){
isUpdated = false;
for (int j = 0; j< edgeCnt; j++){
Edge e = edges[j];
if (d[e.from] != INT_MAX && d[e.to]> d[e.from] + e.cost){
d[e.to] = d[e.from] + e.cost;
isUpdated = true;
if (i == verCnt - 1)
return true;
}
}
}
return false;
}
4-3 최적화 코드
위의 두가지 과정을 나누어서 하면 중복 코드(Overlap code) 가 있고, 반복을 한번더 실행 하기떄문에 비 효율적이다.
따라서 두코드를 합쳐보자.
int N, M;
vector<list<pair<int, int> > > G;
bool bellman_ford(int pos) {
vector<int> d(N);
bool b;
fill(d.begin(), d.end(), MAXN);
d[pos] = 0;
for (int i = 0; i < N; i++){
b = false;
for (int j = 0; j < G.size();j++){
for (auto jt = G[j].begin(); jt != G[j].end(); jt++){
if (d[j] != MAXN && d[jt->first]>d[j] + jt->second){
d[jt->first]=d[j] + jt->second;
b = true;
}
}
}
}
return !b;
}
마지막으로 아래의 그림을 한번더 보면 완벽히 이해가 된다.
아래는 벨만-포드를 이용해 풀 수 있는 문제 이다.
Copyright (C) 2016 (HwangDaeHyeon) all rights reserved.
Modifyed By KimBom at 2016. 05. 03...