C++ でフロイド・ウォーシャル アルゴリズムを使用する方法

C での Floyd-Warshall アルゴリズムの使用方法

Floyd-Warshall アルゴリズムは、有向重み付きノードのすべてのペア間の最短パスを見つけるために使用される方法です。グラフ、アルゴリズム。動的計画法の考え方を採用し、ノードペア間の距離情報を継続的に更新することで最終的に最短経路（つまり、最小の重み）を取得します。

C では、隣接行列 (隣接行列) を使用してグラフの構造を表現し、フロイド-ウォーシャル アルゴリズムを通じて最短パスを解くことができます。

隣接行列は、各ノード間の重み (距離) を記録する 2 次元配列です。 2 つのノード間に直接的な接続がない場合は、より大きな数値 (無限など) を使用してそれを表します。

以下は、C で Floyd-Warshall アルゴリズムを使用する方法を示すサンプル コードです。

#include <iostream>
using namespace std;

const int INF = 1e9; // 无穷大

void floydWarshall(int graph[][4], int n) {
    int dist[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
        }
    }
  
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出最短路径矩阵
    cout << "最短路径矩阵：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                cout << "INF" << "    ";
            } else {
                cout << dist[i][j] << "    ";
            }
        }
        cout << endl;
    }
}

int main() {
    int graph[4][4] = { {0, 5, INF, 10},
                        {INF, 0, 3, INF},
                        {INF, INF, 0, 1},
                        {INF, INF, INF, 0} };

    floydWarshall(graph, 4);

    return 0;
}

上記のコードでは、4x4 の隣接行列グラフを定義し、INF を使用してそれを示します。側には存在しません。次に、floydWarshall 関数を呼び出し、グラフとノード数を渡します。この関数では、dist 2 次元配列を使用して、現在のノード ペア間の最短パス情報を保存します。

フロイド-ウォーシャル アルゴリズムのメイン ループでは、最終的な最短パス行列が得られるまで dist 配列を継続的に更新します。最後に、読みやすくするために INF を無限大に置き換えて、最短パス行列を出力します。

フロイド・ウォーシャル アルゴリズムの時間計算量は O(n^3) (n はノード数) であるため、大規模なグラフではアルゴリズムの実行が遅くなる可能性があることに注意してください。

この記事が、C の Floyd-Warshall アルゴリズムの理解と使用に役立つことを願っています。

以上がC++ でフロイド・ウォーシャル アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。