Menyemak sama ada laluan antara dua nod dalam graf yang diberikan mewakili laluan terpendek

Untuk menyemak sama ada laluan yang diberikan antara dua pusat graf mematuhi laluan terpendek, anda boleh membandingkan keseluruhan berat tepi sepanjang laluan yang diberikan dengan jarak terpendek antara gabungan pusat yang sama menggunakan laluan laluan terpendek yang boleh dipercayai. , seperti pengiraan Dijkstra atau pengiraan Floyd−Warshall. Jika semua pemberat tepi pada laluan tertentu sepadan dengan pemadaman paling terhad, maka ia mewakili laluan paling mudah. Juga: Jika berat tepi keseluruhan lebih menonjol daripada jarak terpendek, ini menunjukkan bahawa terdapat jarak pendek antara dua pusat dalam graf.

Kaedah penggunaan

• Algoritma Dijkstra

• Floyd−Algoritma Warshall dengan kos penyongsangan tepi

Algoritma Tamak

Pengiraan Dijkstra mungkin merupakan pengiraan traversal graf yang popular digunakan untuk mencari laluan paling terhad antara pusat sumber dan semua pusat lain dalam graf. Dalam hal menyemak sama ada laluan yang diberikan antara dua pusat berkaitan dengan laluan paling terhingga, pengiraan Dijkstra boleh digunakan untuk mengira pemisahan paling terhingga antara pusat-pusat ini. Dengan menjalankan pengiraan Dijkstra dari hab permulaan, kami mendapat selang terhingga untuk semua hab lain. Jika laluan tertentu sepadan dengan jarak paling terhad antara dua hab, maka ia mewakili laluan yang besar dan terpendek. Lain-lain: Jika laluan yang diberikan lebih panjang daripada jarak terpendek yang dikira, ini menunjukkan bahawa terdapat laluan yang lebih pendek dalam carta.

Algoritma

• Buat laluan terpendek (graf, sumber, destinasi):

• Mulakan satu set "lalu" untuk menyimpan jarak ke tengah, dan mulakan selang rujukan perkataan untuk menyimpan jarak yang paling terhad.

• Tetapkan jarak hab sumber kepada infiniti dan semua jarak hab lain kepada infiniti dalam kamus pemisah.

• Walaupun terdapat nod yang tidak dilawati,

• a. Pusat dengan jarak terkecil dari rujukan perkataan pemisah dipilih dan ditanda sebagai dilawati.

• b. Untuk setiap hab jiran nod semasa:

• Kira selang sementara dengan menambah berat tepi pada jarak nod semasa.

• Jika jarak keadaan kurang daripada jarak penyimpanan, maka jarak pemeriksaan.

• Kembalikan benar jika jarak terpendek dari sumber ke destinasi dalam pemisahan memecah walaupun dengan panjang laluan yang diberikan (laluan yang diberikan mewakili laluan terpendek). Jika tidak, pulangkan palsu.

• Pengiraan ini menggunakan kaedah Dijkstra untuk mengira selang terpendek dan kemudian membandingkan jarak terpendek dari sumber ke destinasi dengan panjang laluan tertentu untuk menentukan sama ada ia adalah laluan terpendek.

Contoh

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

Output

The given path does not represent a shortest path.

Floyd−Algoritma Warshall dengan kos penyongsangan tepi

Pengiraan Floyd-Warshall ialah pengiraan yang diprogramkan secara dinamik yang mencari laluan terpendek antara semua pasangan pusat dalam graf. Dalam hal menyemak sama ada laluan tertentu antara dua pusat berkaitan dengan laluan paling terhad, pengiraan Floyd-Warshall boleh digunakan untuk mengira pemisahan terpendek antara semua set pusat dalam graf. Dengan membandingkan jarak terpendek yang dikira dengan semua pemberat tepi pada laluan tertentu, kita boleh menentukan sama ada laluan tertentu melibatkan laluan paling terhingga. Jika pemberat tepi keseluruhan sepadan dengan pemisahan terpendek, maka laluan yang diberikan mungkin merupakan laluan paling terhad antara dua pusat dalam graf.

Algoritma

• Buat kekisi 2D mengukur numNodes x numNodes dan mulakannya kepada infiniti (INF) untuk semua set nod.

• Tetapkan penambahan sudut ke penjuru dist kepada 0.

• Untuk setiap tepi penyelarasan (u, v) dengan berat w dalam graf, ubah suai sepenuhnya dist[u][v] kepada w dan dist[v][u] kepada w w_reversal, dengan w_reversal ialah pembalikan Diperolehi dengan cara tepi (v, u).

• Lakukan pengiraan Floyd−Warshall selepas gelung tin:

• Untuk setiap hab separuh jalan dari numNodes hingga 1, lakukan perkara berikut:

• Untuk setiap agregat hab i dan j daripada numNodes kepada 1, tingkatkan dist[i][j] kepada minimum:

• Jarak[i][j]

• Jarak[i][k]Jarak[k][j]

• Selepas pengiraan selesai, dist akan mengandungi pemisahan paling terhad antara semua kumpulan hab, dengan mengambil kira kos penyongsangan tepi.

• Untuk menyemak sama ada laluan yang diberikan antara dua hab (sumber dan destinasi) ialah laluan terpendek, bandingkan panjang laluan yang diberikan dengan jarak [sumber][destinasi]. Jika ya, cara yang diberikan adalah cara yang paling terhad.

Contoh

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

Output

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

Kesimpulan

Artikel ini meneroka cara menyemak sama ada laluan tertentu antara dua pusat graf mewakili laluan paling terhingga. Ia menggambarkan dua kaedah: pengiraan Dijkstra dan pengiraan Floyd-Warshall untuk mendapatkan penyongsangan tepi. Penggunaan kod dalam C menggambarkan pengiraan ini. Ia juga menerangkan secara ringkas pengiraan dan kegunaannya. Artikel ini bertujuan untuk membantu pembaca memahami cara mencari kaedah yang paling terhad dalam graf dan menentukan sama ada kaedah yang diberikan sudah pasti yang paling mudah.

Atas ialah kandungan terperinci Menyemak sama ada laluan antara dua nod dalam graf yang diberikan mewakili laluan terpendek. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!