So verwenden Sie den Dijkstra-Algorithmus in C++

Wie verwende ich den Dijkstra-Algorithmus in C++?

Dijkstras Algorithmus ist ein gieriger Algorithmus, der verwendet wird, um den kürzesten Weg zwischen zwei Eckpunkten in einem gewichteten gerichteten Graphen zu finden. Seine Kernidee besteht darin, den kürzesten Weg schrittweise zu erweitern, indem der kürzeste Abstand vom Startscheitelpunkt zu anderen Scheitelpunkten kontinuierlich aktualisiert wird.

Im Folgenden wird die Verwendung von C++ zur Implementierung des Dijkstra-Algorithmus vorgestellt und spezifische Codebeispiele gegeben.

Die Implementierung des Dijkstra-Algorithmus erfordert die folgenden Schritte:

Schritt 1: Initialisierung.

Zuerst müssen wir einige Datenstrukturen initialisieren, einschließlich des Startscheitelpunkts start, des Arrays dist für die kürzeste Entfernung und des besuchten Arrays für den Besuchsstatus. Der Startscheitelpunktstart gibt den Startpunkt des kürzesten Pfades an, das Kürzeste-Distanz-Array dist wird verwendet, um den aktuell kürzesten Abstand vom Startscheitelpunkt zu anderen Scheitelpunkten aufzuzeichnen, und das besuchte Zugriffsstatus-Array wird verwendet, um zu markieren, ob der Scheitelpunkt besucht wurde .

Schritt 2: Initialisieren Sie das Array mit der kürzesten Entfernung.

Initialisieren Sie den kürzesten Abstand vom Startscheitelpunkt zu anderen Scheitelpunkten bis ins Unendliche und initialisieren Sie den kürzesten Abstand vom Startscheitelpunkt zu sich selbst auf 0. Markiert außerdem den Startscheitelpunkt als besucht.

Schritt 3: Aktualisieren Sie das Array mit den kürzesten Entfernungen.

Wenn für alle Scheitelpunkte neben dem Startscheitelpunkt ein kürzerer Pfad durch den Startscheitelpunkt gefunden werden kann, aktualisieren Sie das Array mit den kürzesten Entfernungen. Die spezifische Aktualisierungsmethode besteht darin, den Abstand vom Startscheitelpunkt zum aktuellen Scheitelpunkt plus das Gewicht der Kante vom Startscheitelpunkt zum aktuellen Scheitelpunkt zu addieren und ihn mit dem ursprünglichen kürzesten Abstand vom aktuellen Scheitelpunkt zu vergleichen.

Schritt 4: Wählen Sie den nächstgelegenen Scheitelpunkt aus.

Wählen Sie aus den nicht besuchten Scheitelpunkten den Scheitelpunkt aus, der dem Startscheitelpunkt am nächsten liegt, als nächsten zu besuchenden Scheitelpunkt.

Schritt 5: Wiederholen Sie die Schritte 3 und 4.

Wiederholen Sie die Schritte 3 und 4, bis alle Eckpunkte besucht wurden. Schließlich wird im Array dist mit der kürzesten Entfernung die kürzeste Entfernung vom Startscheitelpunkt zu jedem Scheitelpunkt gespeichert.

Das Folgende ist ein Codebeispiel, das C++ verwendet, um den Dijkstra-Algorithmus zu implementieren:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

vector<int> dijkstra(vector<vector<int>>& graph, int start) {
    int numVertices = graph.size();

    vector<int> dist(numVertices, INT_MAX); // 最短距离数组
    vector<bool> visited(numVertices, false); // 访问状态数组

    dist[start] = 0;

    for (int i = 0; i < numVertices - 1; i++) {
        int minDist = INT_MAX;
        int minIndex = -1;
        
        // 选取下一个最近顶点
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        visited[minIndex] = true;

        // 更新最短距离数组
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && graph[minIndex][j] && dist[minIndex] != INT_MAX && dist[minIndex] + graph[minIndex][j] < dist[j]) {
                dist[j] = dist[minIndex] + graph[minIndex][j];
            }
        }
    }

    return dist;
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, 4, 0, 0},
        {2, 0, 1, 3, 0},
        {4, 1, 0, 0, 2},
        {0, 3, 0, 0, 3},
        {0, 0, 2, 3, 0}
    };

    vector<int> shortestDist = dijkstra(graph, 0);

    cout << "起始顶点到各个顶点的最短距离：" << endl;
    for (int i = 0; i < shortestDist.size(); i++) {
        cout << "到顶点 " << i << " 的最短距离为：" << shortestDist[i] << endl;
    }

    return 0;
}

Im obigen Code stellen wir einen gewichteten gerichteten Graphen durch eine zweidimensionale Matrix dar. Jedes Element in der Matrix repräsentiert den Abstand zwischen zwei Eckpunkten Gewicht. Geben Sie schließlich den kürzesten Abstand vom Startscheitelpunkt zu jedem Scheitelpunkt aus.

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