벨만-포드 알고리즘

다익스트라와의 차이점

차이점을 설명하기 위해 다익스트라 알고리즘을 간단히 설명하겠습니다.

시작 정점에 인접한 정점을 조사후 더 작은 값을 가진 정점으로 이동합니다.
이동한 정점의 이웃 정점의 최단기록을 기록합니다. 이미 최단거리가 기록된 정점에 대해 재조사 하지 않습니다.

이 경우 일반적인 상황에서는 원하는 값이 출력될 것이고, 프림 알고리즘은 모든 정점을 조사할 때까지 끝나지 않지만 다익스트라는 원하는 정점까지의 최단거리를 구할시 종료됩니다.

하지만 이는 음수 가중치를 가지는 엣지가 없을 때의 기준입니다. 다익스트라 알고리즘은 바로 마주하는 정점만을 조사하기에 그 이웃의 이웃에 음수 가중치가 있다는 사실을 알 수 없습니다.

이 경우에 벨만-포드 알고리즘을 사용하게 됩니다. 벨만-포드 알고리즘의 구동 방식은 다음과 같습니다.

현재 정점을 0으로 초기화하고, 나머지 정점에 대해서는 무한대로 초기화합니다.
시작 정점에 인접한 정점을 조사후 더 작은 값을 가진 정점으로 이동합니다.
이동한 정점의 이웃 정점의 최단기록을 기록합니다. 이미 최단거리가 기록된 정점도 재조사하여 최단거리를 최신화합니다.

두 알고리즘은 크게 다르지 않지만 벨만-포드알고리즘은 음수 가중치 문제를 해결할 수 있습니다. 하지만 다익스트라 알고리즘에 비해 더 높은 시간 복잡도를 가지게 될 것입니다.

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

#include<iostream>
#include<vector>
#include<climits>
 
using namespace std;
 
struct Edge
{
    int src;
    int dst;
    int weight;
};
 
const int UNKNOWN=INT_MAX;
 
vector<int> BellmanFord(vector<Edge> edges, int V, int start)
{
    vector<int> distance(V, UNKNOWN);
    distance[start]=0;
 
    for(int i=0; i<V-1; i++)
    {
        for(auto& e : edges)
        {
            if(distance[e.src]==UNKNOWN)
                continue;
            if(distance[e.dst]>distance[e.src]+e.weight)
            {
                distance[e.dst]=distance[e.src]+e.weight;
            }
        }  
    }
    return distance;
}
 
int main()
{
    int V=5;
    vector<Edge> edges;
    vector<vector<int>> edge_map {{0,1,3},{1,2,5},{1,3,10},{3,2,-7},{2,4,2}};
    for(auto& e:edge_map)
        edges.emplace_back(Edge {e[0],e[1],e[2]});
    int start =0;
    vector<int> distance = BellmanFord(edges,V,start);
 
    cout<<"["<<start<<"번 정점으로 부터 최소거리"<<"]"<<endl;
 
    for(int i =0; i<distance.size(); i++)
    {
        if(distance[i]==UNKNOWN)
            cout<<i<<"번 정점 : 방문하지 않음!"<<endl;
        else
            cout<<i<<"번 정점 : "<<distance[i]<<endl;
    }
}

실행 결과

그래프

가중치

|가중치| |-|-|-|-|-|:-:| |0|-|-|-|-|0| |0|1|-|-|-|3| |0|1|3|2|-|6| |0|1|3|-|-|13| |0|1|3|2|4|8|

음수 가중치 사이클

만일 한 사이클의 총 합이 음수일 경우를 가정해보겠습니다.

이 경우 B, C, D 정점의 엣지의 총합이 음수가 나오게 됩니다. 이 경우 최단 경로를 찾지 않고, 해당 사이클을 도는 것이 가중치 값이 적게 나올것이라 생각할 것입니다.
해당 오류를 발견하는 것은 어렵지 않습니다. 정점의 최단 경로를 구하는데에는 $(정점의수 - 1)$ 번의 단계만을 거치면 되는데, 그 보다 많이 반복하여 찾은 최단 경로는 음수 사이클을 거친 최단 경로 일것이기 때문입니다.
그러한 이유로 마지막에 다시 모든 엣지를 검사하여 기존에 구한 값보다 적은 가중치를 가지게 된다면, 이는 음수 사이클이 있는 경우일 것이고 이 경우에 벨만-포드 알고리즘으로는 정확한 값을 가질 수 없을 것입니다.

#include<iostream>
#include<vector>
#include<climits>
 
using namespace std;
 
struct Edge
{
    int  src;
    int dst;
    int weight;
};
 
const int UNKNOWN=INT_MAX;
 
vector<int> BellmanFord(vector<Edge> edges, int V, int start)
{
    vector<int> distance(V, UNKNOWN);
    distance[start]=0;
 
    for(int i=0; i<V-1; i++)
    {
        for(auto& e : edges)
        {
            if(distance[e.src]==UNKNOWN)
                continue;
            if(distance[e.dst]>distance[e.src]+e.weight)
            {
                cout<<"음수 가중치 사이클 발견!"<<endl;
                return {};
            }
        }  
    }
    return distance;
}
 
 
int main()
{
    int V=6;
    vector<Edge> edges;
    vector<vector<int>> edge_map {{0,1,3},{1,3,-8},{2,1,3},{2,5,5},{3,2,3},{2,4,2},{4,5,-1},{5,1,8}};
    for(auto& e:edge_map)
        edges.emplace_back(Edge {e[0],e[1],e[2]});
    int start =0;
    vector<int> distance = BellmanFord(edges,V,start);
 
    if(!distance.empty())
    {
        cout<<"["<<start<<"번 정점으로 부터 최소거리"<<"]"<<endl;
 
        for(int i =0; i<distance.size(); i++)
        {
            if(distance[i]==UNKNOWN)
                cout<<i<<"번 정점 : 방문하지 않음!"<<endl;
            else
                cout<<i<<"번 정점 : "<<distance[i]<<endl;
        }
    }
}