[c++] 벨만-포드 알고리즘(Bellman-Ford Algorithm) 최단 경로 알고리즘

08 Dec 2023

최단 경로 알고리즘은 그래프에서 가장 짧은 경로를 찾는데 사용되는 알고리즘이다. 이 중 벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서도 사용할 수 있는 장점이 있다.

알고리즘 개요

벨만-포드 알고리즘은 시작 노드에서 다른 모든 노드로의 최단 경로를 찾는 알고리즘이다. 음의 가중치가 있는 그래프에서도 사용이 가능하며, 음의 사이클이 없을 경우, 시작 노드로부터 모든 노드로의 최단 경로를 찾을 수 있다.

시간 복잡도

벨만-포드 알고리즘의 시간 복잡도는 O(V*E)이다. 여기서 V는 노드의 수, E는 간선의 수를 나타낸다.

코드 예시

다음은 C++로 작성된 벨만-포드 알고리즘의 간단한 예시이다.

#include <iostream>
#include <vector>

struct Edge {
    int source, destination, weight;
};

void bellmanFord(std::vector<Edge> edges, int numNodes, int source) {
    std::vector<int> distance(numNodes, INT_MAX);
    distance[source] = 0;

    for (int i = 1; i <= numNodes - 1; i++) {
        for (const auto& edge : edges) {
            if (distance[edge.source] != INT_MAX && distance[edge.destination] > distance[edge.source] + edge.weight) {
                distance[edge.destination] = distance[edge.source] + edge.weight;
            }
        }
    }

    for (const auto& edge : edges) {
        if (distance[edge.source] != INT_MAX && distance[edge.destination] > distance[edge.source] + edge.weight) {
            std::cout << "Graph contains negative weight cycle" << std::endl;
            return;
        }
    }

    for (int i = 0; i < numNodes; i++) {
        std::cout << "Distance from node " << source << " to node " << i << " is " << distance[i] << std::endl;
    }
}

int main() {
    std::vector<Edge> edges = {{0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2}, {3, 4, 5}, {2, 4, 4}};
    int numNodes = 5;
    int source = 0;

    bellmanFord(edges, numNodes, source);

    return 0;
}

요약

벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서도 사용 가능한 최단 경로 알고리즘이다. 알고리즘의 시간 복잡도는 O(V*E)이며, 시작 노드로부터 다른 모든 노드로의 최단 경로를 찾을 수 있다. 그러나 음의 사이클이 있는 경우에는 정확한 결과를 얻을 수 없다.