C++ Dijkstra算法如何进行路径恢复

在使用Dijkstra算法求解最短路径问题时，可以通过记录每个节点的前驱节点来实现路径的恢复。具体步骤如下：

在初始化时，除了记录每个节点的最短距离之外，还需要记录每个节点的前驱节点。可以使用一个数组predecessor[]来保存前驱节点的信息，初始时前驱节点为-1表示没有前驱节点。
在更新节点的最短距离时，如果发现节点v的最短距离被更新了，就把节点v的前驱节点设为u，即predecessor[v] = u。
当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[]数组一直回溯，直到到达起点节点。

最新问答

相关标签