Comment utiliser l'algorithme du chemin le plus court en C++

Comment utiliser l'algorithme du chemin le plus court en C++

L'algorithme du chemin le plus court est l'un des algorithmes clés de la théorie des graphes, qui est utilisé pour déterminer le chemin le plus court entre deux sommets. Dans le langage C++, de nombreuses bibliothèques sont fournies pour implémenter les algorithmes de chemin le plus court, tels que l'algorithme de Dijkstra et l'algorithme de Floyd-Warshall. Cet article vous donnera une introduction détaillée sur la façon d'utiliser ces deux algorithmes et fournira des exemples de code correspondants.

1. Algorithme de Dijkstra

L'algorithme de Dijkstra est un algorithme glouton utilisé pour résoudre le problème du plus court chemin à source unique dans les graphes orientés pondérés. Ce qui suit est un exemple de code qui utilise le langage C++ pour implémenter l'algorithme de Dijkstra :

#include <iostream>
#include <vector>
#include <queue>

const int INF = 1e9;

void dijkstraAlgorithm(int start, const std::vector<std::vector<std::pair<int, int>>>& graph, std::vector<int>& distance) {
    int n = graph.size();
    distance.resize(n, INF);
    distance[start] = 0;

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int dist = pq.top().first;
        pq.pop();

        if (dist > distance[u]) {
            continue;
        }

        for (const auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
                pq.push({distance[v], v});
            }
        }
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<std::pair<int, int>>> graph(n);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    int start;
    std::cin >> start;

    std::vector<int> distance;
    dijkstraAlgorithm(start, graph, distance);

    for (int i = 0; i < n; ++i) {
        std::cout << "Distance from " << start << " to " << i << " is " << distance[i] << std::endl;
    }

    return 0;
}

Le code ci-dessus implémente l'algorithme de Dijkstra. Tout d’abord, lisez le nombre de nœuds n et le nombre d’arêtes m du graphique à partir de l’entrée. Ensuite, une liste de contiguïté est créée pour représenter la structure du graphique, et les informations sur les contours sont stockées dans la liste de contiguïté. Ensuite, lisez le début du nœud de départ. Enfin, appelez la fonction dijkstraAlgorithm pour calculer le chemin le plus court entre le nœud de départ et les autres nœuds et affichez le résultat.

2. Algorithme de Floyd-Warshall

L'algorithme de Floyd-Warshall est utilisé pour résoudre le problème du chemin le plus court entre tous les sommets d'un graphe orienté pondéré. Ce qui suit est un exemple de code qui utilise le langage C++ pour implémenter l'algorithme Floyd-Warshall :

#include <iostream>
#include <vector>

const int INF = 1e9;

void floydWarshallAlgorithm(const std::vector<std::vector<int>>& graph, std::vector<std::vector<int>>& distance) {
    int n = graph.size();

    distance = graph;

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (distance[i][k] != INF && distance[k][j] != INF && distance[i][k] + distance[k][j] < distance[i][j]) {
                    distance[i][j] = distance[i][k] + distance[k][j];
                }
            }
        }
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> graph(n, std::vector<int>(n, INF));

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        graph[u][v] = w;
    }

    std::vector<std::vector<int>> distance;
    floydWarshallAlgorithm(graph, distance);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (distance[i][j] == INF) {
                std::cout << "No path from " << i << " to " << j << std::endl;
            } else {
                std::cout << "Distance from " << i << " to " << j << " is " << distance[i][j] << std::endl;
            }
        }
    }

    return 0;
}

Le code ci-dessus implémente l'algorithme Floyd-Warshall. Tout d’abord, lisez le nombre de nœuds n et le nombre d’arêtes m du graphique à partir de l’entrée. Ensuite, une matrice de contiguïté est créée pour représenter la structure du graphique, et les informations de bord sont stockées dans la matrice de contiguïté. Enfin, appelez la fonction floydWarshallAlgorithm pour calculer le chemin le plus court entre tous les sommets et afficher le résultat.

Avec les exemples de code ci-dessus, vous pouvez apprendre à utiliser l'algorithme de Dijkstra et l'algorithme de Floyd-Warshall en C++ pour résoudre le problème du chemin le plus court. J'espère que cet article vous sera utile et améliorera votre compréhension de l'algorithme du chemin le plus court.

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!