So verwenden Sie den Kürzeste-Pfad-Algorithmus in C++

So verwenden Sie den Kürzeste-Pfad-Algorithmus in C++

Der Kürzeste-Pfad-Algorithmus ist einer der Schlüsselalgorithmen in der Graphentheorie, der zur Bestimmung des kürzesten Pfades zwischen zwei Eckpunkten verwendet wird. In der Sprache C++ werden viele Bibliotheken bereitgestellt, um Algorithmen für kürzeste Pfade zu implementieren, beispielsweise den Dijkstra-Algorithmus und den Floyd-Warshall-Algorithmus. In diesem Artikel erhalten Sie eine detaillierte Einführung in die Verwendung dieser beiden Algorithmen und entsprechende Codebeispiele.

1. Dijkstras Algorithmus

Dijkstras Algorithmus ist ein Greedy-Algorithmus, der zur Lösung des Single-Source-Shortest-Path-Problems in gewichteten gerichteten Graphen verwendet wird. Das Folgende ist ein Codebeispiel, das die Sprache C++ verwendet, um den Dijkstra-Algorithmus zu implementieren:

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

Der obige Code implementiert den Dijkstra-Algorithmus. Lesen Sie zunächst die Anzahl der Knoten n und die Anzahl der Kanten m des Graphen aus der Eingabe ab. Anschließend wird eine Adjazenzliste erstellt, um die Struktur des Diagramms darzustellen, und Kanteninformationen werden in der Adjazenzliste gespeichert. Lesen Sie als Nächstes den Startknotenstart. Rufen Sie abschließend die Funktion dijkstraAlgorithm auf, um den kürzesten Pfad vom Startknoten zu anderen Knoten zu berechnen und das Ergebnis auszugeben.

2. Floyd-Warshall-Algorithmus

Der Floyd-Warshall-Algorithmus wird verwendet, um das Problem des kürzesten Pfades zwischen allen Eckpunkten in einem gewichteten gerichteten Graphen zu lösen. Das Folgende ist ein Codebeispiel, das die Sprache C++ verwendet, um den Floyd-Warshall-Algorithmus zu implementieren:

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

Der obige Code implementiert den Floyd-Warshall-Algorithmus. Lesen Sie zunächst die Anzahl der Knoten n und die Anzahl der Kanten m des Graphen aus der Eingabe ab. Anschließend wird eine Adjazenzmatrix erstellt, um die Struktur des Diagramms darzustellen, und die Kanteninformationen werden in der Adjazenzmatrix gespeichert. Rufen Sie abschließend die Funktion floydWarshallAlgorithm auf, um den kürzesten Pfad zwischen allen Scheitelpunkten zu berechnen und das Ergebnis auszugeben.

Mit den obigen Codebeispielen können Sie lernen, wie Sie den Dijkstra-Algorithmus und den Floyd-Warshall-Algorithmus in C++ verwenden, um das Problem des kürzesten Pfades zu lösen. Ich hoffe, dieser Artikel wird Ihnen hilfreich sein und Ihr Verständnis des Kürzeste-Weg-Algorithmus verbessern.

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