Djikstra算法求解最短路径问题

小咪咪 2024-04-17 06:00 55阅读 0赞

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    using namespace std;
    const int INF=0x3f3f3f3f;
    int mp[1001][1001];
    int d[1001];
    bool vis[1001];
    vector<int> ans;
    int n,m,st,ed;
    void Djikstra(int st)
    {
        memset(vis,0,sizeof(vis));
        int i;
        for(i=1;i<=n;i++)
        {
            d[i]=INF;
        }
        d[st]=0;
        while(true)
        {
            int v=-1;
            //从集合以外的点里面找到距离起点最近的点
            for(i=1;i<=n;i++)
            {
                if(vis[i]==false&&(v==-1||d[i]<d[v]))
                {
                    v=i;
                }
            }
            //说明所有的点都在集合内 此时跳出循环
            if(v==-1)
            {
                break;
            }
            //将v加入集合
            vis[v]=true;
            //用新加入集合的点v更新与其相邻的点距离起点的最短路径
            //之所以不更新集合内的点是因为集合内的点的d的值已经是最小的了
            for(i=1;i<=n;i++)
            {
                if(vis[i]==false)
                {
                    d[i]=min(d[i],d[v]+mp[v][i]);
                }
            }
        }
    }
    int main()
    {
        scanf("%d%d%d%d",&n,&m,&st,&ed);
        int i,j;
        for(i=1;i<=n;i++)
        {
            for(j=i;j<=n;j++)
            {
                mp[i][j]=INF;
                mp[j][i]=INF;
            }
        }
        for(i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b]=min(c,mp[a][b]);
            mp[b][a]=mp[a][b];
        }
        Djikstra(st);
        printf("%d\n",d[ed]);
        //找出行走路线
        int now=ed;
        ans.push_back(now);
        while(true)
        {
            if(now==st)
            {
                break;
            }
            for(i=1;i<=n;i++)
            {
                if(mp[now][i]<INF&&d[now]-mp[now][i]==d[i])
                {
                    ans.push_back(i);
                    now=i;
                    break;
                }
            }
        }
        int len=ans.size();
        for(i=len-1;i>=0;i--)
        {
            if(i<len-1)
                printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
        return 0;
    }

**找出最短路径的长度是多少：**

设一个集合set，vis\[i\]=true表示顶点i在set中，vis\[i\]=false表示顶点i不在set中。

设一个数组d，d\[i\]表示顶点i与起点之间的最短距离。

起初将vis都初始化为false，将d都初始化为无穷大INF。

起点为st，将d\[st\]设为0，表示起点st到它自己的最短路径长度是0。

**每次都从set之外的顶点中选取一个距离起点最近的顶点v，将其加入set；**

**利用顶点v更新与顶点v相邻的set之外的顶点i与起点之间的最短距离d\[i\]。**

直到所有顶点都已加入set，此时跳出循环。

**找出最短路径经过的点：**

**第一种算法（自己想出来的）：**

**最短路径一定是最短路径更新出来的**。

设数组ans为最终结果。从终点ed开始往前找，与ed相邻的顶点i，只有当ed的最短路径长度的d\[ed\]减去ed与i之间的距离mp\[i\]\[ed\]是i的最短路径长度d\[i\]时，d\[ed\]才可能是从d\[i\]更新得到的，将i加入ans。**之所以说“可能”，是因为最短路径可能不只一条，但ans中最终存储的结果一定是最短路径之一**。

同理，一直找到起点st跳出循环。

此时ans中的元素从后往前找就是最短路径依次经过的顶点。

**第二种算法（更为普遍通用的算法）：**

**开一个数组pre\[n\]，存储最短路径中当前结点的前一个结点，最后由终点一步一步找到起点，在将一个点加入set的同时，就完成了这一维护，根据pre数组逆着往前找就经过了从终点到起点的最短路径，将这一路径做一个reverse操作，就得到了从起点到终点的最短路径**。

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    using namespace std;
    const int INF=0x3f3f3f3f;
    int mp[1001][1001];
    int d[1001];
    bool vis[1001];
    int pre[1001];
    vector<int> ans;
    int n,m,st,ed;
    void Djikstra(int st)
    {
        memset(vis,0,sizeof(vis));
        int i;
        for(i=1;i<=n;i++)
        {
            d[i]=INF;
        }
        d[st]=0;
        while(true)
        {
            int v=-1;
            //从集合以外的点里面找到距离起点最近的点
            for(i=1;i<=n;i++)
            {
                if(vis[i]==false&&(v==-1||d[i]<d[v]))
                {
                    v=i;
                }
            }
            //说明所有的点都在集合内 此时跳出循环
            if(v==-1)
            {
                break;
            }
            //将v加入集合
            vis[v]=true;
            //用新加入集合的点v更新与其相邻的点距离起点的最短路径
            //之所以不更新集合内的点是因为集合内的点的d的值已经是最小的了
            for(i=1;i<=n;i++)
            {
                if(vis[i]==false)
                {
                    if(d[v]+mp[v][i]<d[i])
                    {
                        d[i]=d[v]+mp[v][i];
                        pre[i]=v;
                    }
                }
            }
        }
    }
    int main()
    {
        scanf("%d%d%d%d",&n,&m,&st,&ed);
        int i,j;
        for(i=1;i<=n;i++)
        {
            for(j=i;j<=n;j++)
            {
                mp[i][j]=INF;
                mp[j][i]=INF;
            }
        }
        for(i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b]=min(c,mp[a][b]);
            mp[b][a]=mp[a][b];
        }
        Djikstra(st);
        printf("%d\n",d[ed]);
        //找出行走路线
        int now=ed;
        while(true)
        {
            ans.push_back(now);
            if(now==st)
            {
                break;
            }
            now=pre[now];
        }
        int len=ans.size();
        for(i=len-1;i>=0;i--)
        {
            if(i<len-1)
                printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
        return 0;
    }

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[20200227123106884.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/ff4b6b903d0f401687c21edebfbed798.jpg