Vérifie si le chemin entre deux nœuds dans le graphique donné représente le chemin le plus court

Pour vérifier si un chemin donné entre deux centres d'un graphique est conforme au chemin le plus court, vous pouvez comparer le poids total du bord le long du chemin donné avec la distance la plus courte entre la même combinaison de centres en utilisant un chemin fiable. Calculs , comme le calcul de Dijkstra ou le calcul de Floyd−Warshall. Si tous les poids des bords sur un chemin donné correspondent à la suppression la plus limitée, alors cela représente le chemin le plus simple. Également : si le poids global du bord est plus important que la distance la plus courte, cela indique qu'il existe une courte distance entre les deux centres dans le graphique.

Méthode à utiliser

• Algorithme de Dijkstra

• Algorithme Floyd−Warshall avec coût d'inversion de bord

Algorithme gourmand

Le calcul de Dijkstra est probablement un calcul de parcours de graphe populaire utilisé pour trouver le chemin le plus limité entre un centre source et tous les autres centres d'un graphe. Dans le cas de vérifier si un chemin donné entre deux centres est lié au chemin le plus fini, le calcul de Dijkstra peut être utilisé pour calculer la séparation la plus finie entre ces centres. En exécutant le calcul de Dijkstra à partir du hub de départ, nous obtenons les intervalles les plus finis pour tous les autres hubs. Si un itinéraire donné correspond à la distance la plus limitée entre deux hubs, il représente alors un itinéraire substantiel et le plus court. Autres : si l'itinéraire donné est plus long que la distance la plus courte calculée, cela indique qu'il existe un itinéraire plus court dans la carte.

Algorithme

• Créer le chemin le plus court (graphique, source, destination) :

• Initialisez un ensemble de "passé" pour stocker la distance jusqu'au centre, et initialisez un intervalle de référence de mot pour stocker la distance la plus limitée.

• Définissez l'espacement du hub source à l'infini et l'espacement de tous les autres hubs à l'infini dans le dictionnaire des séparateurs.

• Bien qu'il existe des nœuds non visités,

• a. Le centre le plus éloigné de la référence du mot séparateur est sélectionné et marqué comme visité.

• b. Pour chaque hub voisin du nœud actuel :

• Calculez l'intervalle temporaire en ajoutant le poids du bord à la distance du nœud actuel.

• Si l'espacement des conditions est inférieur à l'espacement de stockage, alors la distance d'inspection.

• Renvoie vrai si la distance la plus courte entre la source et la destination dans la séparation est égale à la longueur du chemin donnée (le chemin donné représente le chemin le plus court). Sinon, retournez false.

• Ce calcul utilise la méthode de Dijkstra pour calculer l'intervalle le plus court, puis compare la distance la plus courte entre la source et la destination avec une longueur de chemin donnée pour déterminer s'il s'agit du chemin le plus court.

Exemple

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

Sortie

The given path does not represent a shortest path.

Algorithme Floyd−Warshall avec coût d'inversion de bord

Le calcul Floyd-Warshall est un calcul programmé dynamiquement qui trouve le chemin le plus court entre toutes les paires de centres d'un graphique. Dans le cas de vérifier si un chemin donné entre deux centres est lié au chemin le plus limité, le calcul de Floyd-Warshall peut être utilisé pour calculer la séparation la plus courte entre tous les ensembles de centres du graphique. En comparant la distance la plus courte calculée à tous les poids de bord sur un chemin donné, nous pouvons déterminer si un chemin donné implique le chemin le plus limité. Si les poids globaux des bords correspondent à la séparation la plus courte, alors le chemin donné est probablement le chemin le plus limité entre deux centres du graphique.

Algorithme

• Créez un réseau 2D mesurant numNodes x numNodes et initialisez-le à l'infini (INF) pour tous les ensembles de nœuds.

• Réglez l'addition coin à coin de dist sur 0.

• Pour chaque arête de coordination (u, v) de poids w dans le graphique, modifiez complètement dist[u][v] en w et dist[v][u] en w w_reversal, où w_reversal est l'inversion obtenue grâce à bord (v, u).

• Effectuer le calcul Floyd−Warshall après la boucle standard :

• Pour chaque hub à mi-chemin de numNodes à 1, procédez comme suit :

• Pour chaque agrégat de hubs i et j de numNodes à 1, améliorez dist[i][j] au minimum de :

• Distance[i][j]

• Distance[i][k]Distance[k][j]

• Une fois le calcul terminé, dist contiendra la séparation la plus limitée entre tous les groupes de hubs, en tenant compte des coûts d'inversion de bord.

• Pour vérifier si un itinéraire donné entre deux hubs (source et destination) est l'itinéraire le plus court, comparez la longueur de l'itinéraire donné avec la distance [source][destination]. Si tel est le cas, la voie indiquée est la voie la plus limitée.

Exemple

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

Sortie

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

Conclusion

Cet article explique comment vérifier si un chemin donné entre deux centres d'un graphe représente le chemin le plus fini. Il illustre deux méthodes : le calcul de Dijkstra et le calcul de Floyd-Warshall pour obtenir des inversions de bord. L'utilisation du code en C illustre ces calculs. Il explique également brièvement les calculs et leurs utilisations. Cet article est destiné à aider les lecteurs à comprendre comment trouver la méthode la plus limitée dans un graphique et à déterminer si une méthode donnée est sans aucun doute la plus simple.

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!