So verwenden Sie den Floyd-Warshall-Algorithmus in C++

So verwenden Sie den Floyd-Warshall-Algorithmus in C++

Der Floyd-Warshall-Algorithmus ist ein Algorithmus, der verwendet wird, um den kürzesten Pfad zwischen allen Knotenpaaren in einem gerichteten gewichteten Graphen zu finden. Es übernimmt die Idee der dynamischen Programmierung und erhält schließlich den kürzesten Weg (d. h. das minimale Gewicht), indem es die Abstandsinformationen zwischen Knotenpaaren kontinuierlich aktualisiert.

In C++ können Sie die Adjazenzmatrix (Adjazenzmatrix) verwenden, um die Struktur des Diagramms darzustellen und den kürzesten Weg durch den Floyd-Warshall-Algorithmus zu lösen.

Die Adjazenzmatrix ist ein zweidimensionales Array, das das Gewicht (den Abstand) zwischen den einzelnen Knoten aufzeichnet. Wenn zwischen zwei Knoten keine direkte Verbindung besteht, verwenden Sie zur Darstellung eine größere Zahl (z. B. Unendlich).

Das Folgende ist ein Beispielcode, der zeigt, wie der Floyd-Warshall-Algorithmus in C++ verwendet wird:

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

Im obigen Code definieren wir ein 4x4-Adjazenzmatrixdiagramm und verwenden INF, um nicht vorhandene Kanten darzustellen. Rufen Sie dann die Funktion floydWarshall auf und übergeben Sie den Graphen und die Anzahl der Knoten. In der Funktion verwenden wir das zweidimensionale Array dist, um die kürzesten Pfadinformationen zwischen dem aktuellen Knotenpaar zu speichern.

In der Hauptschleife des Floyd-Warshall-Algorithmus aktualisieren wir kontinuierlich das dist-Array, bis wir die endgültige Matrix des kürzesten Pfads erhalten. Schließlich geben wir die Matrix des kürzesten Pfads aus und ersetzen INF zur einfacheren Lesbarkeit durch Unendlich.

Bitte beachten Sie, dass der Algorithmus bei großen Diagrammen möglicherweise langsamer läuft, da die zeitliche Komplexität des Floyd-Warshall-Algorithmus O(n^3) beträgt, wobei n die Anzahl der Knoten ist.

Ich hoffe, dieser Artikel kann Ihnen helfen, den Floyd-Warshall-Algorithmus in C++ zu verstehen und zu verwenden.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Floyd-Warshall-Algorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!