檢查給定的圖中兩個節點之間的路徑是否表示最短路徑

要檢查圖表的兩個中心之間的給定路徑是否符合最短路徑，可以透過使用可靠的最短路徑將沿著給定路徑的整個邊緣權重與相同中心組合之間的最短距離進行比較方式計算，例如Dijkstra 計算或Floyd−Warshall 計算。如果給定路徑上的所有邊權重與最有限的刪除相匹配，那麼它就代表最簡單的路徑。另外：如果整個邊權重比最短距離更突出，則表示圖表中兩個中心之間存在較短的距離。

使用的方法

• Dijkstra 演算法

• 具有邊緣反轉成本的 Floyd−Warshall 演算法

貪心演算法

Dijkstra 的計算可能是一種流行的圖表遍歷計算，用於發現圖表中來源中心與所有其他中心之間最有限的路徑。在檢查兩個中心之間的給定路徑是否與最有限路徑相關的情況下，Dijkstra 的計算可用於計算這些中心之間的最有限間隔。透過從起始樞紐運行 Dijkstra 的計算，我們得到所有其他樞紐的最有限的間隔。如果給定的路線與兩個樞紐之間的最有限距離相匹配，那麼它就表示一條實質性且最短的路線。其他：如果給定的路線比計算的最短距離長，則表示圖表中存在較短的路線。

演算法

• 建立最短路徑（圖形、來源、目的地）：

• #初始化一組「過去」來儲存去往中心的距離，並初始化一個單字參考間隔來儲存最有限的距離。

• 在分隔字典中將來源集線器的間隔設為無限，並將所有其他中心的間隔設為無限。

• 雖然存在未存取的節點，

• a。選擇與分隔詞參考距離最小的中心並將其標記為已訪問。

• b。對於目前節點的每個鄰居集線器：

• #透過將邊權重加到目前節點的距離來計算臨時間隔。

• 如果條件間距小於存放間距，則檢修距離。

• 如果在分離中從來源到目標的最短距離與給定路徑長度收支平衡，則傳回 true（給定路徑表示最短路徑）。其他情況，傳回 false。

• 此計算利用 Dijkstra 方法來計算最短間隔，然後將從來源到目標的最短距離與給定的路徑長度進行比較，以確定是否為最短的路徑.

#範例

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

輸出

The given path does not represent a shortest path.

具有邊緣反轉成本的 Floyd−Warshall 演算法

Floyd-Warshall 計算是一種動態程式計算，用於發現圖表中所有中心對之間的最短路徑。在檢查兩個中心之間的給定路徑是否與最有限路徑相關的情況下，Floyd-Warshall 計算可用於計算圖表中所有中心集之間的最短間隔。透過將計算得到的最短距離與給定路徑上的全部邊權重進行比較，我們就可以確定給定路徑是否涉及最有限的路徑。如果整個邊權重與最短的間隔相匹配，則此時給定的路徑可能是圖表中兩個中心之間最有限的路徑。

演算法

• 製作一個測量 numNodes x numNodes 的二維格子，並為所有節點集將其初始化為無限 (INF)。

• 將 dist 的角對角加法設定為 0。

• 對於圖表中權重為w 的每個協調邊(u, v)，將dist[u][v] 徹底修改為w，將dist[v][u] 修改為w w_reversal，其中w_reversal 是反轉透過邊（v，u）的方式取得。

• 在固定迴圈後執行 Floyd−Warshall 計算：

• 對於從 numNodes 到 1 之間的每個中途集線器，請執行以下操作：

• 對於從 numNodes 到 1 的集線器 i 和 j 的每個聚合，將 dist[i][j] 改進到以下值中的最小值：

• 距離[i][j]

• 距離[i][k]距離[k][j]

• 計算完成後，考慮到邊緣反轉成本，dist 將包含所有集線器組之間最有限的間隔。

• 要檢查兩個樞紐（來源和目標）之間的給定路線是否為最簡短的路線，請將給定路線的長度與距離 [來源] [目的地] 進行比較。如果是的話，給定的方式是最有限的方式。

範例

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

輸出

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

結論

本文探討如何檢查圖表的兩個中心之間的給定路徑是否代表最有限的路徑。它闡明了兩種方法：Dijkstra 計算和獲取邊緣反轉的 Floyd-Warshall 計算。 C 中的程式碼用法說明了這些計算。它還簡要說明了計算及其用途。本文旨在幫助讀者了解如何在圖表中找到最有限的方法，並確定給定的方法是否無疑是最簡單的。

以上是檢查給定的圖中兩個節點之間的路徑是否表示最短路徑的詳細內容。更多資訊請關注PHP中文網其他相關文章！