C++에서 Bellman-Ford 알고리즘을 사용하는 방법

C++에서 Bellman-Ford 알고리즘을 사용하는 방법

Bellman-Ford 알고리즘은 그래프의 단일 소스 지점에서 다른 모든 정점까지의 최단 경로를 찾는 데 사용되는 알고리즘입니다. 음의 가중치 간선이 포함된 그래프를 처리할 수 있으므로 네트워크 라우팅, 금융 시장 분석 및 기타 분야에서 널리 사용됩니다. 이 기사에서는 C++에서 Bellman-Ford 알고리즘을 사용하는 방법을 소개하고 코드 예제를 제공합니다.

Bellman-Ford 알고리즘의 핵심 아이디어는 최적의 솔루션에 도달할 때까지 완화 연산(Relaxation)을 통해 추정된 최단 경로를 지속적으로 업데이트하는 것입니다. 시간 복잡도는 O(V * E)입니다. 여기서 V는 그래프의 정점 수이고 E는 간선 수입니다.

다음은 C++를 사용하여 Bellman-Ford 알고리즘을 구현하기 위한 샘플 코드입니다.

#include <iostream>
#include <vector>

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

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

    // Relaxation
    for (int i = 1; i < numVertices; i++) {
        for (const auto& edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;
            if (distance[u] != INT_MAX && distance[v] > distance[u] + w) {
                distance[v] = distance[u] + w;
            }
        }
    }

    // Check for negative cycle
    for (const auto& edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int w = edge.weight;
        if (distance[u] != INT_MAX && distance[v] > distance[u] + w) {
            std::cout << "图中存在负权回路
";
            return;
        }
    }

    // 输出最短路径
    for (int i = 0; i < numVertices; i++) {
        if (distance[i] == INT_MAX) {
            std::cout << "源点无法到达顶点 " << i << "
";
        } else {
            std::cout << "源点到顶点 " << i << " 的最短路径为: " << distance[i] << "
";
        }
    }
}

int main() {
    std::vector<Edge> graph = { 
        {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 numVertices = 5;
    int source = 0;

    BellmanFord(graph, numVertices, source);

    return 0;
}

위 코드에서는 에지의 시작점(소스), 끝점(대상) 및 끝점을 포함하는 에지(Edge) 구조를 정의합니다. 무게(무게).

BellmanFord 함수는 모서리 목록, 그래프의 정점 수 및 소스 포인트를 인수로 받습니다. 먼저 거리 배열 거리를 초기화하고 소스 점의 거리를 0으로 설정하며 다른 꼭지점의 거리를 무한대로 설정합니다.

그런 다음 V-1 라운드의 이완 작업을 수행하여 매번 가장자리 세트를 탐색하고 최단 경로를 업데이트하려고 합니다. 가장자리를 완화하여 더 짧은 경로를 얻을 수 있는 경우 대상 정점까지의 거리가 업데이트됩니다. 이런 방법으로 소스 포인트에서 다른 꼭지점까지의 최단 경로를 찾을 수 있습니다.

마지막으로 모든 모서리를 다시 순회하여 음의 가중치 주기가 있는지 확인합니다. 완화 작업 후에도 가장자리가 대상 정점의 거리를 계속 업데이트할 수 있다면 이는 그래프에 음의 가중치 루프가 있음을 의미합니다.

코드의 최종 출력은 최단 경로입니다. 정점까지의 거리가 여전히 무한하다면 소스 포인트가 정점에 도달할 수 없다는 의미이고, 그렇지 않으면 소스 포인트에서 정점까지의 최단 경로가 출력됩니다.

위는 C++를 사용하여 Bellman-Ford 알고리즘을 구현한 코드 예제입니다. 필요에 따라 수정하고 확장할 수 있습니다. 이 알고리즘은 음의 가중치 간선을 가진 그래프를 다룰 때 매우 유용합니다.

위 내용은 C++에서 Bellman-Ford 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!