阅读量:0
在使用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[]数组一直回溯，直到到达起点节点。
