Dijkstra-路径还原输出最短路的路径

浅浅的花香味﹌ 2022-08-22 15:21 118阅读 0赞

在求解最短距离时，满足dis\[j\]=dis\[k\]+cost\[k\]\[j\]的顶点k，就是最短路上的顶点j的前趋节点。

以[POJ 2387][]的题目和代码为例来修改：

/*
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院
    * All rights reserved.
    * 文件名称：dijkstra.cpp
    * 作    者：单昕昕
    * 完成日期：2016年3月30日
    * 版 本 号：v1.0
    */
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <algorithm>
    #define MAXN 1010
    #define INF 0xfffffff//0X代表16进制，后面是数字，十进制是4294967295
    using namespace std;
    int cost[MAXN][MAXN],dis[MAXN],prev[MAXN],n,t;
    bool used[MAXN];//标识是否使用过
    
    void dijkstra(int s)
    {
        memset(used,0,sizeof(used));
        fill(dis,dis+n+1,INF);
        fill(used,used+n+1,false);
        fill(prev,prev+n+1,-1);
        dis[s]=0;
        while(true)
        {
            int v=-1;
            //从未使用过的顶点中选择一个距离最小的顶点
            for(int u=0; u<n; ++u)
                if(!used[u]&&(v==-1||dis[u]<dis[v]))
                    v=u;
            if(v==-1) break;
            used[v]=true;
            for(int u=0; u<=n; ++u)
                if(dis[u]>dis[v]+cost[v][u])
                {
                    dis[u]=dis[v]+cost[v][u];
                    prev[u]=v;
                }
        }
    }
    
    vector<int> get_path(int t)//到顶点n的最短路
    {
        vector<int> path;
        for(; t!=-1; t=prev[t])
            path.push_back(t);
        reverse(path.begin(),path.end());
        return path;
    }
    
    int main()
    {
        int a,b,l;
        while(scanf("%d%d",&t,&n)!=EOF)
        {
            for(int i=0; i<=n; ++i)
                for(int j=0; j<=n; ++j)
                    cost[i][j]=INF;//手动初始化，不能fill了……
            for(int i=0; i<t; i++)
            {
                scanf("%d%d%d",&a,&b,&l);
                if(l<cost[a][b])
                    cost[a][b]=cost[b][a]=l;//无向图
            }
            dijkstra(1);
            printf("%d\n",dis[n]);
            //路径还原，输出路径
            vector<int> path;
            path=get_path(n);
            for(int i=0; i<path.size(); ++i)
                cout<<path[i]<<" ";
            cout<<endl;
        }
        return 0;
    }
    /*
    5 5
    1 2 20
    1 3 10
    3 4 20
    4 5 20
    1 5 100
    */

关键函数：

vector<int> get_path(int t)//到顶点n的最短路
    {
        vector<int> path;
        for(; t!=-1; t=prev[t])
            path.push_back(t);
        reverse(path.begin(),path.end());
        return path;
    }

[POJ 2387]: http://blog.csdn.net/mikasa3/article/details/51018035