So verwenden Sie den Bellman-Ford-Algorithmus in C++

So verwenden Sie den Bellman-Ford-Algorithmus in C++

Der Bellman-Ford-Algorithmus ist ein Algorithmus, der verwendet wird, um den kürzesten Weg von einem einzelnen Quellpunkt zu allen anderen Eckpunkten in einem Diagramm zu finden. Es kann Diagramme verarbeiten, die Kanten mit negativem Gewicht enthalten, und wird daher häufig im Netzwerkrouting, in der Finanzmarktanalyse und in anderen Bereichen eingesetzt. In diesem Artikel wird die Verwendung des Bellman-Ford-Algorithmus in C++ vorgestellt und Codebeispiele bereitgestellt.

Die Kernidee des Bellman-Ford-Algorithmus besteht darin, den geschätzten kürzesten Weg durch Entspannungsoperationen (Relaxation) kontinuierlich zu aktualisieren, bis die optimale Lösung erreicht ist. Seine zeitliche Komplexität beträgt O(V * E), wobei V die Anzahl der Eckpunkte im Diagramm und E die Anzahl der Kanten ist.

Das Folgende ist ein Beispielcode für die Implementierung des Bellman-Ford-Algorithmus mit 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;
}

Im obigen Code definieren wir eine Kantenstruktur (Kante), einschließlich des Startpunkts (Quelle), des Endpunkts (Ziel) und der Kante Gewicht (Gewicht).

Die BellmanFord-Funktion empfängt als Argumente eine Liste von Kanten, die Anzahl der Eckpunkte im Diagramm und den Quellpunkt. Zunächst wird der Abstand des Abstandsarrays initialisiert, der Abstand des Quellpunkts auf 0 und der Abstand anderer Scheitelpunkte auf unendlich gesetzt.

Führen Sie dann die V-1-Runde der Entspannungsoperation durch, wobei Sie jedes Mal den Kantensatz durchlaufen und versuchen, den kürzesten Pfad zu aktualisieren. Wenn durch Entspannen einer Kante ein kürzerer Pfad erreicht werden kann, wird der Abstand zum Zielscheitelpunkt aktualisiert. Auf diese Weise kann der kürzeste Weg vom Quellpunkt zu anderen Eckpunkten gefunden werden.

Abschließend durchlaufen wir noch einmal alle Kanten und prüfen, ob ein negativer Gewichtszyklus vorliegt. Wenn eine Kante nach der Entspannungsoperation immer noch den Abstand des Zielscheitelpunkts aktualisieren kann, bedeutet dies, dass im Diagramm eine Schleife mit negativer Gewichtung vorhanden ist.

Die endgültige Ausgabe des Codes ist der kürzeste Weg. Wenn der Abstand zu einem Scheitelpunkt immer noch unendlich ist, bedeutet dies, dass der Quellpunkt den Scheitelpunkt nicht erreichen kann. Andernfalls wird der kürzeste Weg vom Quellpunkt zum Scheitelpunkt ausgegeben.

Das Obige ist ein Codebeispiel für die Verwendung von C++ zur Implementierung des Bellman-Ford-Algorithmus. Sie können es je nach Bedarf modifizieren und erweitern. Dieser Algorithmus ist sehr nützlich, wenn Sie mit Diagrammen mit negativen Gewichtskanten arbeiten. Ich hoffe, er wird Ihnen hilfreich sein.

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