음수 간선을 가지는 그래프의 최단 경로: 벨만-포드 알고리즘

최단 경로 알고리즘은 대표적으로 플로이드 워셜, 다익스트라 등등 있지만 이 중에서도 한 노드에서 다른 노드까지의 최단 경로에는 다익스트라 알고리즘이 사용된다. 하지만 다익스트라 알고리즘은 양수에서만 동작한다. 왜 다익스트라 알고리즘은 양수 간선에서만 해를 찾을 수 있을까?

 

 

 

벨만 포드 알고리즘의 대표적인 문제들

11657 타임머신

문제를 해석하면 위와 같다. 한 노드에서 다른 노드까지의 최단 경로인데, 이때 음수 간선이 있을 수 있다.

따라서 벨만 포드 알고리즘을 사용하면 쉽게 해결할 수 있는 문제이다.

 

구현

// 11657 타임머신
#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> graph[501];
long dist[501];	// long type이어야 함
int N, M;
bool cycle;

// 벨만 포드 알고리즘: 음의 간선이 있을 때의 최단 거리 구하기
void bellmanFord(int start)
{
    // 시작점까지의 거리는 0
    dist[start] = 0;
    
    // N-1번 테스트하고 마지막에 업데이트 했을 때 업데이트 가능해진다면 음수 사이클이 있는 것임
    for(int count = 1;count <= N;count++)
    {
        for(int i = 1;i <= N;i++)
        {
            for(int j = 0;j < graph[i].size();j++)
            {
                int next = graph[i][j].first;
                int w = graph[i][j].second;
                
                if (dist[i] != 1e9 && dist[next] > dist[i] + w)
                {
                    dist[next] = dist[i] + w;
                    
                    // 마지막 업데이트때 업데이트 가능해지면 음수 순환이 있는 것임
                    if (count == N)
                    {
                        cycle = true;
                        return;
                    }
                }
            }
        }
    }
    
  
}
int main()
{
    cin.tie(0);
    
    cin>>N>>M;
    
    for(int i = 0;i < M;i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        
        graph[a].push_back({b, c});
    }
    
    fill_n(dist, N + 1, 1e9);
    
    cycle = false;
    bellmanFord(1);
    
    if (cycle == true)
        cout<<-1<<"\n";
    else
    {
        for(int i = 2;i <= N;i++)
        {
            if (dist[i] == 1e9)
                cout<<-1<<"\n";
            else
                cout<<dist[i]<<"\n";
        }
    }
    
    return 0;
}