[c++] 벨만-포드 알고리즘

08 Dec 2023

알고리즘 설명

벨만-포드 알고리즘은 다음과 같이 동작합니다:

출발 노드의 최단 거리를 0으로 설정하고, 다른 모든 노드의 최단 거리를 무한대로 초기화합니다.
모든 간선에 대해 반복하면서 현재 노드까지의 최단 거리와 해당 간선의 가중치를 고려하여 다음 노드까지의 최단 거리를 업데이트합니다.
모든 간선에 대해 위 과정을 (노드의 수 - 1)번 반복합니다. 이 과정을 통해 최단 거리가 갱신될 가능성이 있는 모든 경우를 고려할 수 있습니다.
(노드의 수 - 1)번 반복 이후에도 최단 거리가 갱신된다면 음수 사이클이 존재하는 것이므로 음수 사이클이 존재한다는 것을 알리는 에러를 발생시킵니다.

시간 복잡도

벨만-포드 알고리즘의 시간 복잡도는 O(V*E)입니다. V는 노드의 수, E는 간선의 수를 나타냅니다.

예제 코드

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int src, dest, weight;
};

void bellmanFord(vector<Edge> edges, int V, int E, int start) {
    vector<int> dist(V, INT_MAX);
    dist[start] = 0;

    for (int i = 0; i < V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u = edges[j].src;
            int v = edges[j].dest;
            int weight = edges[j].weight;

            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    for (int i = 0; i < E; i++) {
        int u = edges[i].src;
        int v = edges[i].dest;
        int weight = edges[i].weight;

        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
            cout << "음수 사이클이 존재합니다." << endl;
            return;
        }
    }

    for (int i = 0; i < V; i++) {
        cout << "노드 " << i << "까지의 최단 거리: " << dist[i] << endl;
    }
}

int main() {
    int V = 5;
    int E = 8;
    vector<Edge> edges = {
        {0, 1, -1},
        {0, 2, 4},
        {1, 2, 3},
        {1, 3, 2},
        {1, 4, 2},
        {3, 2, 5},
        {3, 1, 1},
        {4, 3, -3}
    };
    int start = 0;

    bellmanFord(edges, V, E, start);

    return 0;
}

벨만-포드 알고리즘은 음수 가중치를 가진 그래프에서도 사용할 수 있기 때문에 프로그래밍에서 많은 유용성을 가지고 있습니다.

참고문헌:

Introduction to the Design and Analysis of Algorithms, by Anany Levitin