Comment utiliser l'algorithme de Dijkstra en C++

Comment utiliser l'algorithme de Dijkstra en C++ ?

L'algorithme de Dijkstra est un algorithme glouton utilisé pour trouver le chemin le plus court entre deux sommets dans un graphe orienté pondéré. Son idée principale est d'étendre progressivement le chemin le plus court en mettant continuellement à jour la distance la plus courte entre le sommet de départ et les autres sommets.

Ce qui suit présentera comment utiliser C++ pour implémenter l'algorithme de Dijkstra et donnera des exemples de code spécifiques.

La mise en œuvre de l'algorithme de Dijkstra nécessite les étapes suivantes :

Étape 1 : Initialisation.

Tout d'abord, nous devons initialiser certaines structures de données, notamment le début du sommet de départ, la distance du tableau de distance la plus courte et le tableau d'état de la visite visité. Le début du sommet de départ spécifie le point de départ du chemin le plus court, le tableau de distance le plus court dist est utilisé pour enregistrer la distance la plus courte actuelle entre le sommet de départ et les autres sommets, et le tableau d'état d'accès visité est utilisé pour marquer si le sommet a été visité. .

Étape 2 : Initialisez le tableau de distance la plus courte.

Initialisez la distance la plus courte du sommet de départ aux autres sommets à l'infini, et initialisez la distance la plus courte du sommet de départ à lui-même à 0. Marque également le sommet de départ comme visité.

Étape 3 : Mettez à jour le tableau de distance la plus courte.

Pour tous les sommets adjacents au sommet de départ, si un chemin plus court peut être trouvé à travers le sommet de départ, mettez à jour le tableau de distance le plus court. La méthode de mise à jour spécifique consiste à ajouter la distance entre le sommet de départ et le sommet actuel plus le poids de l'arête entre le sommet de départ et le sommet actuel, et à la comparer avec la distance la plus courte d'origine à partir du sommet actuel.

Étape 4 : Sélectionnez le prochain sommet le plus proche.

Sélectionnez le sommet le plus proche du sommet de départ parmi les sommets non visités comme prochain sommet à visiter.

Étape 5 : Répétez les étapes 3 et 4.

Répétez les étapes 3 et 4 jusqu'à ce que tous les sommets aient été visités. Enfin, ce qui est stocké dans le tableau de distance la plus courte dist est la distance la plus courte entre le sommet de départ et chaque sommet.

Ce qui suit est un exemple de code qui utilise C++ pour implémenter l'algorithme de Dijkstra :

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

Dans le code ci-dessus, nous représentons un graphe orienté pondéré à travers une matrice bidimensionnelle. Chaque élément de la matrice représente la distance entre deux sommets. poids. Enfin, affichez la distance la plus courte entre le sommet de départ et chaque sommet.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!