91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

C++ Dijkstra算法如何進行路徑恢復

c++
小樊
82
2024-07-25 17:30:19
欄目: 編程語言

在使用Dijkstra算法求解最短路徑問題時,可以通過記錄每個節點的前驅節點來實現路徑的恢復。具體步驟如下:

  1. 在初始化時,除了記錄每個節點的最短距離之外,還需要記錄每個節點的前驅節點。可以使用一個數組predecessor[]來保存前驅節點的信息,初始時前驅節點為-1表示沒有前驅節點。

  2. 在更新節點的最短距離時,如果發現節點v的最短距離被更新了,就把節點v的前驅節點設為u,即predecessor[v] = u。

  3. 當Dijkstra算法執行完畢后,就可以通過predecessor[]數組來恢復路徑。假設要求從起點s到終點t的最短路徑,可以從終點t開始,沿著predecessor[]數組一直回溯到起點s,即可得到完整的最短路徑。

以下是一個簡單的示例代碼,展示了如何使用Dijkstra算法和predecessor[]數組來實現路徑的恢復:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

#define INF INT_MAX

void Dijkstra(vector<vector<pair<int, int>>> &graph, int start, int end) {
    int n = graph.size();
    vector<int> dist(n, INF);
    vector<int> predecessor(n, -1);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push(make_pair(0, start));

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

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

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                predecessor[v] = u;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    // Path recovery
    vector<int> path;
    int cur = end;
    while (cur != -1) {
        path.push_back(cur);
        cur = predecessor[cur];
    }

    // Print the shortest path
    cout << "Shortest path from " << start << " to " << end << ": ";
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << path[i] << " ";
    }
    cout << endl;
}

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

    // Add edges to the graph
    graph[0].push_back(make_pair(1, 7));
    graph[0].push_back(make_pair(2, 9));
    graph[0].push_back(make_pair(5, 14));
    graph[1].push_back(make_pair(2, 10));
    graph[1].push_back(make_pair(3, 15));
    graph[2].push_back(make_pair(3, 11));
    graph[2].push_back(make_pair(5, 2));
    graph[3].push_back(make_pair(4, 6));
    graph[4].push_back(make_pair(5, 9));

    int start = 0;
    int end = 4;

    Dijkstra(graph, start, end);

    return 0;
}

在以上示例中,我們首先使用Dijkstra算法求解從節點0到節點4的最短路徑,然后通過predecessor[]數組恢復完整路徑并打印出來。路徑恢復的關鍵在于沿著predecessor[]數組一直回溯,直到到達起點節點。

0
仁怀市| 潞城市| 封丘县| 两当县| 陇西县| 洪江市| 桐城市| 托克逊县| 绥江县| 诸城市| 北宁市| 尼玛县| 长宁区| 合山市| 印江| 永嘉县| 福贡县| 和平区| 内黄县| 广汉市| 珲春市| 舞阳县| 霍山县| 高陵县| 喜德县| 靖宇县| 霸州市| 花莲市| 西充县| 靖江市| 磐石市| 天津市| 恩平市| 吉林省| 龙山县| 高清| 青河县| 榆中县| 堆龙德庆县| 沙坪坝区| 汝南县|