벨만-포드 알고리즘 (Bellman-Ford Algorithm)

벨만-포드 알고리즘은 다익스트라 알고리즘과는 다른 방법으로 그래프에서의 단일 시작점에서의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 $O(ElogV)$의 매우 빠른 시간복잡도를 갖고 있지만, 음수간선에 대해 최단거리를 구하지 못한다는 단점이 있다. 벨만-포드 알고리즘은 이를 보완하여 음수 간선에 대해서도 최단거리를 구할 수 있게 해 준다.

기본적으로, 그래프에서 각 간선을 "완화"하는 작업을 반복한 후, 이러한 과정을 적질히 계속하여 결국은 모든 노드에 대해 최단 거리를 구해 낸다.

 

일단, 모든 간선에 대해 이와 같은 성질이 성립한다. 

u에서 v로의 간선 w가 존재한다면, $dist[v]<=dist[u]+w$ ($dist[x]$=$x$까지의 최단거리)

이 성질을 이용하여 만약 $dist[v]>dist[u]+w$ 라면 $dist[v]=dist[u]+w$ 로 조금 더 작게 만들어 줄 수 있다. 이를 "완화"라 하자.

 

이제, 이러한 완화 과정을 몇번 반복해야 할까, 정점의 개수가 V개인 그래프에서 시작점으로부터 끝점까지 지나야 하는 간선의 최대 개수는 V-1 개이다. k번째 완화에는 시작점으로부터 k개의 간선을 거쳐 도달할 수 있는 정점까지의 최단거리를 정확하게 구할 수 있다.

 

마지막으로, 과연 음수 사이클은 어떻게 판단할 수 있을까?

음수 사이클이 존재 한다면 한번 더 완화한다면 값이 계속 줄어들 수 있음을 의미 한다. 따라서 V-1 번 벨만포드를 돌린 후, 마지막 V번째에 dist 배열이 완화가 일어난다면 음수 사이클이 존재한다고 할 수 있다.

또한, 최단경로의 실제 경로를 구하고 싶다면, 이는 마지막을 완화가 일어난 지점을 찾으면 된다.

 

시간 복잡도는 바깥 루프가 $V$, 내부 루프가 $E$, 즉 $O(VE)$ 이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;
const int INF = 987654321;

int n, m;
vector<pii> adj[MAXN+10];
int dist[MAXN+10], par[MAXN+10];
bool negcycle;

int main()
{
    int i, j;

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({v, w});
    }

    for(i=1; i<=n; i++) dist[i]=INF;
    dist[1]=0;

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            for(auto nxt : adj[j])
            {
                if(dist[j]!=INF && dist[j]+nxt.second<dist[nxt.first])
                {
                    par[nxt.first]=j;
                    dist[nxt.first]=dist[j]+nxt.second;
                    if(i==n) negcycle=true;
                }
            }
        }
    }

    if(negcycle) return !printf("NEGCYCLE");
    for(i=2; i<=n; i++) printf("%d\n", dist[i]!=INF?dist[i]:-1);
}