36. Bellman-Ford 알고리즘

벨만-포드 알고리즘이란?

음의 가중치를 가지는 그래프에서 최단거리를 구하는 알고리즘이다.

음의 가중치를 가지는 그래프에서 다익스트라 알고리즘은 사용할 수 없는 것일까?

다익스트라 알고리즘은 각 간선의 가중치가 양수인 경우에만 올바른 결과를 보장하기 때문에 사용할 수 없다.

반면에 벨만-포드 알고리즘은 간선의 가중치가 음수인 경우에도 올바른 결과를 보장한다.

---

벨만-포드 알고리즘 구현

1. 시작 노드를 선택하고, 시작 노드로부터 모든 노드까지의 최단거리를 무한대로 초기화한다. 이때 시작 노드의 최단거리는 0으로 초기화 한다.

2. 모든 간선에 대해 반복한다. 각 반복에서는, 모든 노드에 대해 최단거리를 갱신한다.

3. 모든 노드에 대해 최단 거리를 갱신한 후, 만약 어떤 노드의 최단거리가 갱신된다면, 해당 노드로부터 도달 가능한 모든 노드의 최단거리를 다시 갱신한다.

4. 2~3의 과정을 총 N-1번 반복한다. (N은 그래프 노드의 수)

5. 음의 사이클이 있는 경우, 최단거리를 구할 수 없다. 이를 체크하기 위해 2~4를 한번 더 반복하고 만약 노드의 최단거리가 갱신된다면 음의 사이클이 존재하는 것이다.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_N 1000
#define MAX_M 10000
#define INF INT_MAX

typedef struct {
    int from;
    int to;
    int weight;
} Edge;

int n, m;
Edge edges[MAX_M];
int dist[MAX_N];

void bellman_ford(int start) {
    // 초기화
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }
    dist[start] = 0;

    // 간선을 이용하여 최단거리 갱신
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            int u = edges[j].from;
            int v = edges[j].to;
            int w = edges[j].weight;
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // 음의 사이클 체크
    for (int j = 0; j < m; j++) {
        int u = edges[j].from;
        int v = edges[j].to;
        int w = edges[j].weight;
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            printf("Negative cycle detected.\n");
            return;
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i < m; i++)
        scanf("%d %d %d", &edges[i].from, &edges[i].to, &edges[i].weight);
    
    bellman_ford(0);
    
    for (int i = 0; i < n; i++) 
        printf("%d ", dist[i]);
    
    printf("\n");
    
    return 0;
}

모든 노드를 한 번씩 방문하면서 모든 간선에 대해 최단거리를 갱신한다.

시간복잡도는 O( n m )이다.