如何使用C++中的Floyd-Warshall演算法

如何使用C 中的Floyd-Warshall演算法

Floyd-Warshall演算法是一種用於求解有向加權圖中所有節點對之間最短路徑的演算法.它採用動態規劃的思想，透過不斷更新節點對之間的距離訊息，最終得出最短路徑（即最小權重）。

在C 中，可以使用鄰接矩陣（Adjacency Matrix）來表示圖的結構，並透過Floyd-Warshall演算法來求解最短路徑。

鄰接矩陣是一個二維數組，其中記錄了每個節點之間的權重（距離）。若兩個節點之間沒有直接連接，則以一個較大的數（如無限大）表示。

下面是一個範例程式碼，展示如何使用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的鄰接矩陣graph，並用INF表示不存在的邊。然後，呼叫floydWarshall函數，傳入圖和節點數目。函數中，我們使用dist二維數組保存目前節點對之間的最短路徑資訊。

在Floyd-Warshall演算法的主迴圈中，我們不斷更新dist數組，直到我們得到最終的最短路徑矩陣。最後，我們輸出最短路徑矩陣，將INF替換成無限大，方便閱讀。

請注意，由於Floyd-Warshall演算法的時間複雜度為O(n^3)，其中n為節點數目，因此對於大規模的圖，演算法可能會運作較慢。

希望這篇文章能對你理解並使用C 中的Floyd-Warshall演算法有所幫助。

以上是如何使用C++中的Floyd-Warshall演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！