Cara menggunakan algoritma Floyd-Warshall dalam C++

Cara menggunakan algoritma Floyd-Warshall dalam C++

Algoritma Floyd-Warshall ialah algoritma yang digunakan untuk mencari laluan terpendek antara semua pasangan nod dalam graf berwajaran terarah. Ia menerima pakai idea pengaturcaraan dinamik dan akhirnya memperoleh laluan terpendek (iaitu berat minimum) dengan mengemas kini maklumat jarak antara pasangan nod secara berterusan.

Dalam C++, anda boleh menggunakan matriks bersebelahan (Adjacency Matrix) untuk mewakili struktur graf dan menyelesaikan laluan terpendek melalui algoritma Floyd-Warshall.

Matriks bersebelahan ialah tatasusunan dua dimensi yang merekodkan berat (jarak) antara setiap nod. Jika tiada sambungan langsung antara dua nod, gunakan nombor yang lebih besar (seperti infiniti) untuk mewakilinya.

Berikut ialah contoh kod yang menunjukkan cara menggunakan algoritma Floyd-Warshall dalam C++:

#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;
}

Dalam kod di atas, kami mentakrifkan graf matriks bersebelahan 4x4 dan menggunakan INF untuk mewakili tepi yang tidak wujud. Kemudian, panggil fungsi floydWarshall, lulus dalam graf dan bilangan nod. Dalam fungsi, kami menggunakan tatasusunan dua dimensi dist untuk menyimpan maklumat laluan terpendek antara pasangan nod semasa.

Dalam gelung utama algoritma Floyd-Warshall, kami sentiasa mengemas kini tatasusunan dist sehingga kami mendapat matriks laluan terpendek terakhir. Akhir sekali, kami mengeluarkan matriks laluan terpendek, menggantikan INF dengan infiniti untuk bacaan yang lebih mudah.

Sila ambil perhatian bahawa kerana kerumitan masa algoritma Floyd-Warshall ialah O(n^3), dengan n ialah bilangan nod, algoritma mungkin berjalan lebih perlahan untuk graf berskala besar.

Saya harap artikel ini dapat membantu anda memahami dan menggunakan algoritma Floyd-Warshall dalam C++.

Atas ialah kandungan terperinci Cara menggunakan algoritma Floyd-Warshall dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!