벨만포드 알고리즘

 

다익스트라 알고리즘은 O(NlongN) 안에 한 노드에서 다른 모든 노드에 대한 최단 거리를 찾을 수 있다.

벨만-포드 알고리즘의 경우 O(N^2)으로 최단 거리를 찾는다.

 

벨만-포드 알고리즘이 존재하는 이유는 "음수"값을 가지는 간선이 존재할때 최단 거리를 찾기 위함이다.

음수 간선이 존재할 경우 circuit이 생길 수도 있는데, circuit을 돌 수록 음수 간선에 의해 최단 거리가 계속 줄어들 수도 있다.

하지만, 상식적으로 생각해 본다면, 같은 길을 반복해서 지나가는건 최단 거리가 아니다.

벨만-포드는 이 두가지 경우를 상정할 때 최단 거리를 구할 수 있는 알고리즘이다.

 

벨만-포드의 특징은

- 음수간선이 존재

- Cycle을 돌면 안됨 -> cycle을 돌 경우 탐색 중지

 

라고 할 수 있다.

다익스트라와 유사하게 방문한 노드와 연결된 다른 노드가지의 거리를 비교해서 최단거리를 업데이트 하는데, 음수 간선을 지나는 cycle을 돌아 한 최단거리가 무한히 작아질 수 있다.

이를 방지하기 위해 |V|-1 번의 탐색만 진행한다. (V는 노드의 갯수)

 

1-2-3-4

 

처럼 노드가 존재할 경우, 최대 탐색은 4-1번인 3이기 때문에, 이 이상으로 탐색이 진행되면 cycle을 돌고 있다고 판단되기 때문이다.

 

구현은 단순하다. brute force 처럼 2중 for문을 돌며 한 노드와 연결된 모든 노드에 대해 탐색을 진행하되, cycle을 도는것만 탐지해내면 된다.

 

<소스코드>

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
 
using namespace std;
 
int N,M;
vector<pair<int,int>> v[501];
vector<long long> d;
 
bool cir = false; // cycle 표시용
 
void bell(int s){
    
    d[s] = 0;
    
    for(int i = 1; i<=N; i++){ // i == N(노드 갯수) 까지 오면 cycle을 돌고 있는 것!
        for(int j = 1; j<=N; j++){ // 각 노드를 방문하여 탐색 
            for(auto &n : v[j]){
                if(d[j] == LONG_LONG_MAX) continue; // 한번 방문했던 노드만
                if(d[n.first] > n.second + d[j]){
                    d[n.first] = n.second + d[j];
                    if(i == N){
                        cir = true;
                        
                    }
                }
                
            }
        }
    }
    
    
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>>N>>M;
    
    for(int i = 1; i<=M; i++){
        int a,b,c;
        cin>>a>>b>>c;
        
        v[a].push_back(make_pair(b,c));
        
    }
    
    for(int i = 0; i<=N+1; i++){
        d.push_back(LONG_LONG_MAX);
    }
    
    bell(1);
    
    if(cir == true){
        cout<<"-1"<<endl;
    }
    else{
        for(int i = 2; i <=N; i++){
            if(d[i] == LONG_LONG_MAX)
                cout<<"-1"<<endl;
            else
                cout<<d[i]<<endl;
        }
    }
    
    
    
}