图的五种最短路径算法

迈不过友情╰ 2022-09-16 06:11 158阅读 0赞

本文总结了图的几种最短路径算法的实现：深度或广度优先搜索算法，费罗伊德算法，迪杰斯特拉算法，Bellman-Ford 算法。

1）深度或广度优先搜索算法（解决单源最短路径）

从起点开始访问所有深度遍历路径或广度优先路径，则到达终点节点的路径有多条，取其中路径权值最短的一条则为最短路径。

下面是核心代码：

void dfs(int cur,int dst){
        if(minpath<dst) return;//当前走过的路径大雨之前的最短路径，没有必要再走下去了
        if(cur==en){//临界条件，当走到终点n
           if(minpath>dst){
            minpath=dst;
            return;
           }
        }
         for(int i=1;i<=n;i++){
            if(mark[i]==0&&edge[cur][i]!=inf&&edge[cur][i]!=0){
                mark[i]=1;
                dfs(i,dst+edge[cur][i]);
                mark[i]=0;//需要在深度遍历返回时将访问标志置0
            }
         }
         return;
    }

例：先输入n个节点，m条边，之后输入有向图的m条边，边的前两个元素表示起点和终点，第三个值表示权值，输出1号城市到n号城市的最短距离。

#include<bits/stdc++.h>
    using namespace std;
    #define nmax 110
    #define inf 999999999
    int minpath,n,m,en,edge[nmax][nmax],mark[nmax];//最短路径，节点数，边数，终点，邻接矩阵，节点访问标记
    void dfs(int cur,int dst){
        if(minpath<dst) return;//当前走过的路径大雨之前的最短路径，没有必要再走下去了
        if(cur==en){//临界条件，当走到终点n
           if(minpath>dst){
            minpath=dst;
            return;
           }
        }
         for(int i=1;i<=n;i++){
            if(mark[i]==0&&edge[cur][i]!=inf&&edge[cur][i]!=0){
                mark[i]=1;
                dfs(i,dst+edge[cur][i]);
                mark[i]=0;//需要在深度遍历返回时将访问标志置0
            }
         }
         return;
    }
    int main ()
    {
          while(cin>>n>>m&&n!=0){
            //初始化邻接矩阵
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    edge[i][j]=inf;
                }
                edge[i][i]=0;
            }
          int a,b;
          while(m--){
            cin>>a>>b;
            cin>>edge[a][b];
          }
          minpath=inf;
          memset(mark,0,sizeof(mark));
          mark[1]=1;
          en=n;
          dfs(1,0);
          cout<<minpath<<endl;
          }
    }

程序运行结果如下：

![a321110060ac4a8e82761618c3770773.png][]

2）弗洛伊德算法（解决多源最短路径）：时间复杂度o(n^3),空间复杂度o(n^2)

基本思想：最开始只允许经过1号顶点进行中转，接下来只允许经过1号和2号顶点进行中转.......允许经过1~n号所有顶点进行中转，来不断动态更新任意两点之间的最短距离。即求从i号顶点到j顶点只经过前k号点的最短距离。

分析如下：1，首先构建邻接矩阵edge\[n+1\]\[n+1\],假如现在只允许经过1号节点，求任意两点间的最短距离，很显然edge\[i\]\[j\]=min(edge\[i\]\[j\],edge\[i\]\[1\]+edge\[1\]\[j\]),代码如下：

for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(edge[i][j]>edge[i][1]+edge[1][j]){
                   edge[i][j]=edge[i][1]+edge[1][j];
                }
            }
         }

2.接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短距离，在已经实现了从i号顶点到j号顶点只经过前1号点的最短路程的前提下，现在插入第2号节点，来看看能不能更新最短路径，因此只需在步骤一求得的基础上，进行edge\[i\]\[j\]=min(edge\[i\]\[j\],edge\[i\]\[2\]+edge\[2\]\[j\]);.......

3.很显然，需要n次这样的更新，表示依次插入了1号2号.......n号节点，最后求得的edge\[i\]\[j\]是从i号顶点到j号顶点只经过前n号点的最短路程。因此核心代码如下：

#include<bits/stdc++.h>
    using namespace std;
    #define inf 999999999
    int main ()
    {
        for(int k=1;k<=n;k++){
         for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(edge[k][j]<inf&&edge[i][k]<inf&&edge[i][j]>edge[i][k]+edge[k][j]){
                   edge[i][j]=edge[i][k]+edge[k][j];
                }
            }
         }
         }
    }

例1：寻找最短的从商场到赛场的路线。其中商店在1号节点处，赛场在n号节点处，1~n节点中有m条线路双向连接。

/\*\*\*先输入n，m，在输入m个三元组，n为路口数，m表示有几条路，其中1为商店，n为赛场，三元组分别表示起点终点，和该路径长，输出1到n的最短距离\*\*\*/

#include<bits/stdc++.h>
    using namespace std;
    #define inf 999999999
    #define nmax 110
    int n,m,edge[nmax][nmax];
    int main ()
    {
        int a,b;
        while(cin>>n>>m&&n!=0){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    edge[i][j]=inf;
                }
                edge[i][i]=0;
            }
            while(m--){
               cin>>a>>b;
               cin>>edge[a][b];
               edge[b][a]=edge[a][b];
            }
            for(int k=1;k<=n;k++){
         for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(edge[k][j]<inf&&edge[i][k]<inf&&edge[i][j]>edge[i][k]+edge[k][j]){
                   edge[i][j]=edge[i][k]+edge[k][j];
                }
            }
         }
         }
         cout<<edge[1][n]<<endl;
        }
    }

程序运行结果如下：

![8e8455b22f154815ac81d7d9540a37f8.png][]

3）迪杰斯特拉算法（解决单源最短路径）

基本思想：每次找到离源点（如1号节点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

基本步骤：1，设置标记数组book\[\]：将所有的顶点分为两部分，已知最短路径的顶点集合P和未知最短路径的顶点集合Q，很显然最开始集合P只有源点一个顶点。book\[i\]为1表示在集合P中；

2，设置最短路径数组dst\[\]并不断更新：初始状态下，dst\[i\]=edge\[s\]\[i\](s为源点，edge为邻接矩阵),很显然此时dst\[s\]=0,book\[s\]=1.此时，在集合Q中可选择一个离源点s最近的顶点u加入到P中。并依据以u为新的中心点，对每一条边进行松弛操作（松弛是指由顶点s-->j的途中可以经过点u，并令dst\[j\]=min(dst\[j\],dst\[u\]+edge\[u\]\[j\])）,并令book\[u\]=1;

3，在集合Q中再次选择一个离源点s最近的顶点v加入到P中。并依据v为新的中心点，对每一条边进行松弛操作（即dst\[j\]=min(dst\[j\],dst\[v\]+edge\[v\]\[j\])）,并令book\[v\]=1;

4,重复3，直至集合Q为空。

核心代码如下：

#include<bits/stdc++.h>
    using namespace std;
    #define nmax 110
    #define inf 999999999
    /***构建所有点最短路径数组dst[],且1为源点***/
    int u;/***离源点最近的点***/
    int minx;
    for(int i=1;i<=n;i++) dst[i]=edge[1][i];
    for(int i=1;i<=n;i++) book[i]=0;
    book[1]=1;
    for(int i=1;i<=n-1;i++){
            minx=inf;
        for(int j=1;j<=n;j++){
            if(book[j]==0&&dst[j]<minx){
                minx=dst[j];
                u=j;
            }
        }
        book[u]=1;
        /***更新最短路径数组***/
        for(int k=1;k<=n;k++){
            if(book[k]==0&&dst[k]>dst[u]+edge[u][k]&&edge[u][k]<inf){
                dst[k]=dst[u]+edge[u][k];
            }
        }
    }

例1：给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s，终点t，要求输出起点到终点的最短距离及其花费，如果最短距离是有多条路线，则输出花费最少的。

输入：输入n，m，点的编号是1~n，然后是m行，每行4个数a，b，d，p，表示a和b之间有一条边，且长度为d，花费为p。最后一行是两个数s，t，起点s，终点t。n和m为0时输入结束。（1<n<=1000,0<m<100000,s!=t）

输出：输出一行，有两个数，最短距离及其花费。

分析：由于每条边有长度d和花费p，最好构建变结构体存放。

使用邻接矩阵求解：

#include<bits/stdc++.h>
    using namespace std;
    #define nmax 110
    #define inf 999999999
    struct Edge{
        int len;
        int cost;
    }edge[nmax][nmax];
    int u,n,m,book[nmax],s,t,dst[nmax],spend[nmax];
    int minx;
    int main (){
        while(cin>>n>>m&&n!=0&&m!=0){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    edge[i][j].len=inf;
                    edge[i][j].cost=0;
                }
                edge[i][i].len=0;
            }
            int a,b;
            while(m--){
                cin>>a>>b;
                cin>>edge[a][b].len>>edge[a][b].cost;
                edge[b][a].len=edge[a][b].len;
                edge[b][a].cost=edge[a][b].cost;
            }
            cin>>s>>t;
           for(int i=1;i<=n;i++) {dst[i]=edge[s][i].len;spend[i]=edge[s][i].cost;}
           for(int i=1;i<=n;i++) book[i]=0;
           book[s]=1;
    for(int i=1;i<=n-1;i++){
            minx=inf;
       for(int j=1;j<=n;j++){
            if(book[j]==0&&dst[j]<minx){
                minx=dst[j];
                u=j;
            }
        }
        book[u]=1;
        for(int k=1;k<=n;k++){
            if(book[k]==0&&(dst[k]>dst[u]+edge[u][k].len||(dst[k]==dst[u]+edge[u][k].len&&spend[k]>spend[u]+edge[u][k].cost))&&edge[u][k].len<inf){
                dst[k]=dst[u]+edge[u][k].len;
                spend[k]=spend[u]+edge[u][k].cost;
            }
        }
    }
           cout<<dst[t]<<' '<<spend[t]<<endl;
        }
     }

程序运行结果如下：

![87b3fd5c455a48e99f8d8bb20267b5ea.png][]

4）Bellman-Ford算法（解决负权边，解决单源最短路径，前几种方法不能解决负权边）

主要思想：所有的边进行n-1轮松弛，因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1条边。换句话说，第1轮在对所有的边进行松弛操作后，得到从1号顶点只能经过一条边到达其余各定点的最短路径长度，第2轮在对所有的边进行松弛操作后，得到从1号顶点只能经过两条边到达其余各定点的最短路径长度，........

此外，Bellman-Ford算法可以检测一个图是否含有负权回路：如果经过n-1轮松弛后任然存在dst\[e\[i\]\]>dst\[s\[i\]\]+w\[i\].

例1：对图中含有负权的有向图，输出从1号节点到各节点的最短距离，并判断有无负权回路。

#include<bits/stdc++.h>
    using namespace std;
    #define nmax 1001
    #define inf 999999999
    int n,m,s[nmax],e[nmax],w[nmax],dst[nmax];
    int main ()
    {
           while(cin>>n>>m&&n!=0&&m!=0){
            for(int i=1;i<=m;i++){
                cin>>s[i]>>e[i]>>w[i];
            }
            for(int i=1;i<=n;i++)
                dst[i]=inf;
            dst[1]=0;
            for(int i=1;i<=n-1;i++){
                for(int j=1;j<=m;j++){
                    if(dst[e[j]]>dst[s[j]]+w[j]){
                       dst[e[j]]=dst[s[j]]+w[j];
                    }
                }
            }
            int flag=0;
            for(int i=1;i<=m;i++){
               if(dst[e[i]]>dst[s[i]]+w[i]){
                    flag=1;
            }
           }
           if(flag) cout<<"此图有负权回路"<<endl;
           else{
            for(int i=1;i<=n;i++){
                if(i==1) cout<<dst[i];
                else cout<<' '<<dst[i];
            }
            cout<<endl;
           }
    }
    }

程序运行结果如下：

![6e274de1595f43bbab7b7f795e7fbc74.png][]

5）SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法，它是Bellman-ford队列优化，它是一种十分高效的最短路算法。

实现方法：建立一个队列，初始时队列里只有起始点s，在建立一个数组记录起始点s到所有点的最短路径（初始值都要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里的点去刷新起始点s到所有点的距离的距离，如果刷新成功且刷新的点不在队列中，则把该点加入到队列，重复执行直到队列为空。

此外，SPFA算法可以判断图中是否有负权欢=环，即一个点的入队次数超过N。

#include<bits/stdc++.h>
    using namespace std;
    int n,m,len;
    struct egde{
         int to,val,next;
    }e[200100];
    int head[200100],vis[200100],dis[200100];
    void add(int from,int to,int val){
         e[len].to=to;
         e[len].val=val;
         e[len].next=head[from];
         head[from]=len;
         len++;
    }
    void spfa()
    {
        queue<int>q;
        q.push(1);
        vis[1]=1;
        while(!q.empty())
        {
            int t=q.front();
            q.pop();
            vis[t]=0;
            for(int i=head[t];i!=-1;i=e[i].next){
                int s=e[i].to;
                if(dis[s]>dis[t]+e[i].val){
                    dis[s]=dis[t]+e[i].val;
                    if(vis[s]==0){
                        q.push(s);
                        vis[s]=1;
                    }
                }
            }
        }
     
    }
    int main(){
        int from,to,val;
        while(cin>>n>>m){
            memset(head,-1,sizeof(head));
            memset(vis,0,sizeof(vis));
           /* for(int i=1;i<=n;i++){
                dis[i]=99999999;
            }*/
            memset(dis,0x3f,sizeof(dis));
            dis[1]=0;len=1;
            for(int i=0;i<m;i++){
                cin>>from>>to>>val;
                add(from,to,val);
            }
            spfa();
            for(int i=1;i<=n;i++){
                cout<<dis[i]<<" ";
            }
            cout<<endl;
        }
    }

[a321110060ac4a8e82761618c3770773.png]: /images/20220828/774c6ce8794c41caa2af4c704283dc56.png
[8e8455b22f154815ac81d7d9540a37f8.png]: /images/20220828/b26824e03e4e428999a689165d6bd339.png
[87b3fd5c455a48e99f8d8bb20267b5ea.png]: /images/20220828/f2a0e5e2b8334cf4a275d8ab8d17e55d.png
[6e274de1595f43bbab7b7f795e7fbc74.png]: /images/20220828/79e6c4967c294451bf8ffa80d099b390.png