Comment utiliser l'algorithme Bellman-Ford en C++

Comment utiliser l'algorithme Bellman-Ford en C++

L'algorithme Bellman-Ford est un algorithme utilisé pour trouver le chemin le plus court entre un point source unique et tous les autres sommets d'un graphique. Il peut gérer des graphiques contenant des bords de poids négatifs, il est donc largement utilisé dans le routage de réseau, l'analyse des marchés financiers et d'autres domaines. Cet article explique comment utiliser l'algorithme Bellman-Ford en C++ et fournit des exemples de code.

L'idée principale de l'algorithme de Bellman-Ford est de mettre à jour en permanence le chemin le plus court estimé via une opération de relaxation (relaxation) jusqu'à ce que la solution optimale soit atteinte. Sa complexité temporelle est O(V * E), où V est le nombre de sommets du graphe et E est le nombre d'arêtes.

Ce qui suit est un exemple de code pour implémenter l'algorithme Bellman-Ford en utilisant C++ :

#include <iostream>
#include <vector>

struct Edge {
    int source;
    int destination;
    int weight;
};

void BellmanFord(std::vector<Edge>& edges, int numVertices, int source) {
    std::vector<int> distance(numVertices, INT_MAX);
    distance[source] = 0;

    // Relaxation
    for (int i = 1; i < numVertices; i++) {
        for (const auto& edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;
            if (distance[u] != INT_MAX && distance[v] > distance[u] + w) {
                distance[v] = distance[u] + w;
            }
        }
    }

    // Check for negative cycle
    for (const auto& edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int w = edge.weight;
        if (distance[u] != INT_MAX && distance[v] > distance[u] + w) {
            std::cout << "图中存在负权回路
";
            return;
        }
    }

    // 输出最短路径
    for (int i = 0; i < numVertices; i++) {
        if (distance[i] == INT_MAX) {
            std::cout << "源点无法到达顶点 " << i << "
";
        } else {
            std::cout << "源点到顶点 " << i << " 的最短路径为: " << distance[i] << "
";
        }
    }
}

int main() {
    std::vector<Edge> graph = { 
        {0, 1, -1},
        {0, 2, 4},
        {1, 2, 3},
        {1, 3, 2},
        {1, 4, 2},
        {3, 2, 5},
        {3, 1, 1},
        {4, 3, -3}
    };
    int numVertices = 5;
    int source = 0;

    BellmanFord(graph, numVertices, source);

    return 0;
}

Dans le code ci-dessus, nous définissons une structure de bord (Edge), comprenant le point de départ (source), le point d'arrivée (destination) du bord et poids (poids).

La fonction BellmanFord reçoit en arguments une liste d'arêtes, le nombre de sommets dans le graphe et le point source. Il initialise d'abord la distance du tableau de distance, définit la distance du point source sur 0 et définit la distance des autres sommets à l'infini.

Ensuite, effectuez un cycle d'opération de relaxation V-1, en parcourant le bord défini à chaque fois et en essayant de mettre à jour le chemin le plus court. Si un chemin plus court peut être obtenu en relâchant une arête, la distance jusqu'au sommet cible est mise à jour. De cette façon, le chemin le plus court depuis le point source vers les autres sommets peut être trouvé.

Enfin, nous parcourons à nouveau tous les bords et vérifions s'il y a un cycle de poids négatif. Si une arête peut encore mettre à jour la distance du sommet cible après l'opération de relaxation, cela signifie qu'il y a une boucle de poids négatif dans le graphique.

La sortie finale du code est le chemin le plus court. Si la distance jusqu'à un sommet est toujours infinie, cela signifie que le point source ne peut pas atteindre le sommet, sinon le chemin le plus court depuis le point source jusqu'au sommet est affiché.

Ce qui précède est un exemple de code d'utilisation de C++ pour implémenter l'algorithme Bellman-Ford. Vous pouvez le modifier et l'étendre selon vos besoins. Cet algorithme est très utile lorsqu'il s'agit de graphiques avec des bords de poids négatifs. J'espère qu'il vous sera utile.

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!