本文共 1664 字，大约阅读时间需要 5 分钟。
Dijstra算法不仅可以计算源点到各个顶点的最短距离，还可以记录从源点到达每个顶点的最短路径的前驱节点。以下是详细说明：
理解前驱节点的概念
在Dijstra算法中，我们通常使用一个数组pre来记录每个顶点在最短路径中的前驱节点。pre[v]表示顶点v在最短路径中被访问之前所经过的那个顶点。构造完整路径
通过递归访问pre数组，可以从目标顶点一步步追溯回源点，从而得到完整的最短路径。例如，假设pre[4] = 3，那么顶点4的前驱是顶点3；继续查询pre[3] = 2，顶点3的前驱是顶点2；再查询pre[2] = 1，顶点2的前驱是顶点1。通过这种方式，可以逐步构造出完整的路径。代码实现说明
代码主要包含以下几个部分：pre数组记录前驱节点。代码示例
以下是代码的主要部分：#include#include #include using namespace std;int n, m, s, G[maxSize][maxSize];int d[maxSize];bool vis[maxSize] = {false};int pre[maxSize];void Dijstra(int s) { fill(d, d + maxSize, INF); d[s] = 0; for (int i = 0; i < n; ++i) { int u = -1, min = INF; for (int j = 0; j < n; ++j) { if (!vis[j] && d[j] < min) { u = j; min = d[j]; } } if (u == -1) return; vis[u] = true; for (int v = 0; v < n; ++v) { if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]) { d[v] = d[u] + G[u][v]; pre[v] = u; } } }}void shortPath(int s, int v) { if (s == v) { return; } shortPath(s, pre[v]); cout << v << " ";}int main() { // 初始化前驱数组 for (int i = 0; i < n; ++i) { pre[i] = i; } // 读取输入并初始化邻接矩阵 for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; G[u][v] = w; } Dijstra(s); // 输出最短距离 for (int i = 0; i < n; ++i) { cout << d[i] << " "; } // 输出最短路径 shortPath(s, v);}
通过上述方法，我们可以不仅找到最短距离，还能准确地重建路径，从而实现对最短路径的完整追踪和输出。
转载地址：http://urwg.baihongyu.com/