Comment utiliser l'algorithme Floyd-Warshall en C++

Comment utiliser l'algorithme Floyd-Warshall en C++

L'algorithme Floyd-Warshall est un algorithme utilisé pour trouver le chemin le plus court entre toutes les paires de nœuds dans un graphe pondéré orienté. Il adopte l'idée de programmation dynamique et obtient finalement le chemin le plus court (c'est-à-dire le poids minimum) en mettant continuellement à jour les informations de distance entre les paires de nœuds.

En C++, vous pouvez utiliser la matrice de contiguïté (Adjacency Matrix) pour représenter la structure du graphe et résoudre le chemin le plus court grâce à l'algorithme de Floyd-Warshall.

La matrice de contiguïté est un tableau bidimensionnel qui enregistre le poids (distance) entre chaque nœud. S'il n'y a pas de connexion directe entre deux nœuds, utilisez un nombre plus grand (comme l'infini) pour le représenter.

Ce qui suit est un exemple de code montrant comment utiliser l'algorithme Floyd-Warshall en 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;
}

Dans le code ci-dessus, nous définissons un graphe matriciel de contiguïté 4x4 et utilisons INF pour représenter des arêtes inexistantes. Ensuite, appelez la fonction floydWarshall, en passant le graphique et le nombre de nœuds. Dans la fonction, nous utilisons le tableau bidimensionnel dist pour enregistrer les informations sur le chemin le plus court entre la paire de nœuds actuelle.

Dans la boucle principale de l'algorithme Floyd-Warshall, nous mettons continuellement à jour le tableau dist jusqu'à ce que nous obtenions la matrice finale du chemin le plus court. Enfin, nous générons la matrice du chemin le plus court, en remplaçant INF par l'infini pour une lecture plus facile.

Veuillez noter que puisque la complexité temporelle de l'algorithme Floyd-Warshall est O(n^3), où n est le nombre de nœuds, l'algorithme peut s'exécuter plus lentement pour les graphiques à grande échelle.

J'espère que cet article pourra vous aider à comprendre et à utiliser l'algorithme Floyd-Warshall en C++.

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!