C++ で Bellman-Ford アルゴリズムを使用する方法

C でのベルマン フォード アルゴリズムの使用方法

ベルマン フォード アルゴリズムは、単一のソース ポイントから他のすべての頂点までの最短パスを見つけるために使用される方法です。グラフのアルゴリズムで。負の重みエッジを含むグラフを扱うことができるため、ネットワークルーティング、金融市場分析などの分野で広く使用されています。この記事では、C で Bellman-Ford アルゴリズムを使用する方法を説明し、コード例を示します。

ベルマン・フォード アルゴリズムの中心的な考え方は、最適解に到達するまで、緩和操作 (緩和) を通じて推定最短経路を継続的に更新することです。その時間計算量は 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 中国語 Web サイトの他の関連記事を参照してください。