Dijkstra算法输出最短路径-白红宇的个人博客

Dijkstra算法输出最短路径

发布日期：2021-05-07 22:04:58 浏览次数：12 分类：精选文章

本文共 1664 字，大约阅读时间需要 5 分钟。

Dijstra算法不仅可以计算源点到各个顶点的最短距离，还可以记录从源点到达每个顶点的最短路径的前驱节点。以下是详细说明：

理解前驱节点的概念

在Dijstra算法中，我们通常使用一个数组pre来记录每个顶点在最短路径中的前驱节点。pre[v]表示顶点v在最短路径中被访问之前所经过的那个顶点。

构造完整路径

通过递归访问pre数组，可以从目标顶点一步步追溯回源点，从而得到完整的最短路径。例如，假设pre[4] = 3，那么顶点4的前驱是顶点3；继续查询pre[3] = 2，顶点3的前驱是顶点2；再查询pre[2] = 1，顶点2的前驱是顶点1。通过这种方式，可以逐步构造出完整的路径。

代码实现说明

代码主要包含以下几个部分：

初始化部分：将每个顶点的前驱设置为自己。

输入部分：读取图的边权信息并初始化邻接矩阵。

Dijstra算法核心：使用优先队列实现最短路径计算，同时更新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);}

通过上述方法，我们可以不仅找到最短距离，还能准确地重建路径，从而实现对最短路径的完整追踪和输出。

上一篇：最短路径求解（Dijkstra算法）

下一篇：C++实现Dijkstra算法（单源路径最短算法）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章