C++を使用したFloyd-Warshallアルゴリズムの実装方法

まず、必要なヘッダーファイルをインクルードします。

#include <iostream>
#include <climits>
using namespace std;

次に、頂点の数と辺の数を定義します。

#define V 4  // グラフの頂点の数
#define INF INT_MAX  // 無限大を表す値

最短経路を計算する関数を定義します。

void floydWarshall(int graph[][V]) {
    int dist[V][V];
    // 初期距離を入力グラフと同じに設定
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }
// 中間頂点をすべて経由する場合の最短経路を計算
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                // 頂点kを経由する経路が、直接の経路よりも短い場合は更新
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
// 最短経路の出力
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }
}

以上のコードを使用して、Floyd-Warshallアルゴリズムを実行するためのメイン関数を書きます。

int main() {
    // グラフの隣接行列を定義
    int graph[V][V] = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };
    // Floyd-Warshallアルゴリズムを実行
    floydWarshall(graph);
    return 0;
}

このコードは、4つの頂点を持つグラフの最短経路を計算します。INFは、頂点間の経路が存在しないことを示します。実行すると、最短経路行列が出力されます。

以上が、C++を使用してFloyd-Warshallアルゴリズムを実装する方法の例です。このアルゴリズムは、グラフ内の全ての頂点間の最短経路を見つけるために役立ちます。