Überprüft, ob der Pfad zwischen zwei Knoten im angegebenen Diagramm den kürzesten Pfad darstellt

Um zu überprüfen, ob ein gegebener Pfad zwischen zwei Mittelpunkten des Diagramms dem kürzesten Weg entspricht, können Sie das gesamte Kantengewicht entlang des gegebenen Pfades mit dem kürzesten Abstand zwischen derselben Kombination von Mittelpunkten vergleichen, indem Sie zuverlässige Berechnungen für den kürzesten Weg verwenden , wie die Dijkstra-Berechnung oder die Floyd-Warshall-Berechnung. Wenn alle Kantengewichte auf einem bestimmten Pfad mit der am stärksten eingeschränkten Löschung übereinstimmen, stellt dies den einfachsten Pfad dar. Außerdem: Wenn das Gesamtkantengewicht stärker ausgeprägt ist als der kürzeste Abstand, weist dies darauf hin, dass zwischen den beiden Mittelpunkten im Diagramm ein geringer Abstand besteht.

Anwendungsmethode

• Dijkstra-Algorithmus

• Floyd-Warshall-Algorithmus mit Kanteninversionskosten

Gieriger Algorithmus

Dijkstras Berechnung ist wahrscheinlich eine beliebte Graph-Traversal-Berechnung, die verwendet wird, um den begrenztesten Pfad zwischen einem Quellzentrum und allen anderen Zentren in einem Diagramm zu finden. Im Falle der Überprüfung, ob ein gegebener Weg zwischen zwei Zentren mit dem endlichsten Weg zusammenhängt, kann die Dijkstra-Berechnung verwendet werden, um den endlichsten Abstand zwischen diesen Zentren zu berechnen. Indem wir Dijkstras Berechnung vom Start-Hub aus ausführen, erhalten wir die endlichsten Intervalle für alle anderen Hubs. Wenn eine bestimmte Route der engsten Entfernung zwischen zwei Knotenpunkten entspricht, handelt es sich um eine wesentliche und kürzeste Route. Sonstiges: Wenn die angegebene Route länger als die berechnete kürzeste Entfernung ist, weist dies darauf hin, dass es in der Karte eine kürzere Route gibt.

Algorithmus

• Kürzesten Weg erstellen (Grafik, Quelle, Ziel):

• Initialisieren Sie einen Satz „Vergangenheit“, um den Abstand zum Zentrum zu speichern, und initialisieren Sie ein Wortreferenzintervall, um den engsten Abstand zu speichern.

• Stellen Sie im Trennzeichenwörterbuch den Abstand des Quell-Hubs auf unendlich und den Abstand aller anderen Hubs auf unendlich ein.

• Obwohl es unbesuchte Knoten gibt,

• a. Der Mittelpunkt mit dem geringsten Abstand zur Trennwortreferenz wird ausgewählt und als besucht markiert.

• b. Für jeden Nachbar-Hub des aktuellen Knotens:

• Berechnen Sie das temporäre Intervall, indem Sie das Kantengewicht zum Abstand des aktuellen Knotens addieren.

• Wenn der Zustandsabstand kleiner ist als der Lagerabstand, dann der Inspektionsabstand.

• Gibt „true“ zurück, wenn die kürzeste Entfernung von der Quelle zum Ziel im Abstand die angegebene Pfadlänge überschreitet (der angegebene Pfad stellt den kürzesten Pfad dar). Andernfalls wird false zurückgegeben.

• Diese Berechnung verwendet die Dijkstra-Methode, um das kürzeste Intervall zu berechnen und vergleicht dann die kürzeste Entfernung von der Quelle zum Ziel mit einer gegebenen Weglänge, um zu bestimmen, ob es sich um den kürzesten Weg handelt.

Beispiel

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

bool shortestPath(vector<vector<pair<int, int>>>& graph, int source, int destination, int pathLength) {
    int numNodes = graph.size();
    vector<int> distances(numNodes, INF);
    distances[source] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.emplace(0, source);

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

        if (dist > distances[u])
            continue;

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

            if (dist + weight < distances[v]) {
                distances[v] = dist + weight;
                pq.emplace(distances[v], v);
            }
        }
    }

    return (distances[destination] == pathLength);
}

int main() {
    int numNodes = 6;
    vector<vector<pair<int, int>>> graph(numNodes);

    // Build the graph
    graph[0].emplace_back(1, 2);
    graph[0].emplace_back(2, 5);
    graph[1].emplace_back(3, 4);
    graph[1].emplace_back(4, 1);
    graph[2].emplace_back(3, 2);
    graph[3].emplace_back(4, 3);
    graph[3].emplace_back(5, 6);
    graph[4].emplace_back(5, 2);

    int source = 0;
    int destination = 5;
    int pathLength = 8;

    bool isShortestPath = shortestPath(graph, source, destination, pathLength);

    if (isShortestPath)
        cout << "The given path represents a shortest path." << endl;
    else
        cout << "The given path does not represent a shortest path." << endl;

    return 0;
}

Ausgabe

The given path does not represent a shortest path.

Floyd-Warshall-Algorithmus mit Kanteninversionskosten

Die Floyd-Warshall-Berechnung ist eine dynamisch programmierte Berechnung, die den kürzesten Weg zwischen allen Mittelpunktspaaren in einem Diagramm ermittelt. Um zu überprüfen, ob ein gegebener Weg zwischen zwei Zentren mit dem am stärksten begrenzten Weg zusammenhängt, kann die Floyd-Warshall-Berechnung verwendet werden, um den kürzesten Abstand zwischen allen Sätzen von Zentren im Diagramm zu berechnen. Indem wir die berechnete kürzeste Distanz mit allen Kantengewichten auf einem gegebenen Pfad vergleichen, können wir bestimmen, ob es sich bei einem gegebenen Pfad um den endlichsten Pfad handelt. Wenn die Gesamtkantengewichte mit dem kürzesten Abstand übereinstimmen, ist der angegebene Pfad wahrscheinlich der am stärksten eingeschränkte Pfad zwischen zwei Mittelpunkten im Diagramm.

Algorithmus

• Erstellen Sie ein 2D-Gitter mit den Maßen „numNodes x numNodes“ und initialisieren Sie es für alle Knotensätze auf unendlich (INF).

• Setzen Sie die Ecke-zu-Ecke-Addition von dist auf 0.

• Ändern Sie für jede Koordinationskante (u, v) mit dem Gewicht w im Diagramm dist[u][v] vollständig in w und dist[v][u] in w w_reversal, wobei w_reversal die durch erhaltene Umkehrung ist Kante (v, u).

• Führen Sie eine Floyd-Warshall-Berechnung nach einer Standardschleife durch:

• Für jeden Hub auf halber Strecke von numNodes bis 1 gehen Sie wie folgt vor:

• Verbessern Sie dist[i][j] für jedes Aggregat der Hubs i und j von numNodes auf 1 auf das Minimum von:

• Entfernung[i][j]

• Entfernung[i][k]Entfernung[k][j]

• Nach Abschluss der Berechnung enthält dist den begrenztesten Abstand zwischen allen Hub-Gruppen unter Berücksichtigung der Kanteninversionskosten.

• Um zu überprüfen, ob eine bestimmte Route zwischen zwei Knotenpunkten (Quelle und Ziel) die kürzeste Route ist, vergleichen Sie die Länge der angegebenen Route mit der Entfernung [Quelle][Ziel]. Wenn ja, ist der angegebene Weg der begrenzteste Weg.

Beispiel

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9;

void floydWarshall(vector<vector<int>>& graph, int numNodes) {
    vector<vector<int>> dist(graph); // Distance matrix initialized with the graph

    for (int k = 0; k < numNodes; k++) {
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    // Printing the shortest distances
    cout << "Shortest distances between all pairs of nodes:" << endl;
    for (int i = 0; i < numNodes; i++) {
        for (int j = 0; j < numNodes; j++) {
            if (dist[i][j] == INF)
                cout << "INF ";
            else
                cout << dist[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    int numNodes = 4; // Number of nodes

    // Adjacency matrix representation of the graph with edge weights and edge reversal costs
    vector<vector<int>> graph = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };

    floydWarshall(graph, numNodes);

    return 0;
}

Ausgabe

Shortest distances between all pairs of nodes:
0 5 8 9 
INF 0 3 4 
INF INF 0 1 
INF INF INF 0 

Fazit

In diesem Artikel wird untersucht, wie man überprüft, ob ein gegebener Pfad zwischen zwei Mittelpunkten eines Diagramms den endlichsten Pfad darstellt. Es veranschaulicht zwei Methoden: die Dijkstra-Berechnung und die Floyd-Warshall-Berechnung zum Erhalten von Kanteninversionen. Die Codeverwendung in C veranschaulicht diese Berechnungen. Außerdem werden Berechnungen und ihre Verwendung kurz erläutert. Dieser Artikel soll den Lesern helfen zu verstehen, wie sie die am stärksten eingeschränkte Methode in einem Diagramm finden und feststellen können, ob eine bestimmte Methode zweifellos die einfachste ist.

Das obige ist der detaillierte Inhalt vonÜberprüft, ob der Pfad zwischen zwei Knoten im angegebenen Diagramm den kürzesten Pfad darstellt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!