最短路算法

布满荆棘的人生 2021-11-04 14:46 292阅读 0赞

**解决最短路的问题主要有以下算法：Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法。**

## **1、Dijkstra算法** ##

**参考链接：https://blog.csdn.net/kprogram/article/details/81225176**  
（此算法和普利姆算法求最小生成树类似）  
**注**：Dijkstra算法适用于边权为正的无向和有向图，不适用于有负边权的图

**用途：**

用于求图中指定两点之间的最短路径，或者是指定一点到其它所有点之间的最短路径。实质上是**贪心算法**。

**基本思想：**

1.将图上的初始点看作一个集合S，其它点看作另一个集合

2.根据初始点，求出其它点到初始点的距离d\[i\] （若相邻，则d\[i\]为边权值；若不相邻，则d\[i\]为无限大）

3.选取最小的d\[i\]（记为d\[x\]），并将此d\[i\]边对应的点（记为x）加入集合S

（实际上，加入集合的这个点的d\[x\]值就是它到初始点的最短距离）

4.再根据x，更新跟 x 相邻点 y 的d\[y\]值：d\[y\] = min\{ d\[y\], d\[x\] + 边权值w\[x\]\[y\] \}，因为可能把距离调小，所以这个更新操作叫做松弛操作。

5.重复3，4两步，直到目标点也加入了集合，此时目标点所对应的d\[i\]即为最短路径长度。

void Dijkstra(int v)
    { 
        int i, j, k;
        for(i = 1; i <= n; i++)//dist数组的初始化
        { 
            dist[i] = map[v][i];
            vis[i] = 0;
        }
        dist[v] = 0;
        vis[v] = 1;
    
        for(i = 0; i < n-1; i++)
        { 
            int min = INF, u = v;
            for(j = 1; j <= n; j++)//寻找未标记结点的最小值
            { 
                if(vis[j] == 0 && dist[j] < min)
                { 
                    u = j;
                    min = dist[j];
                }
            }
            vis[u] = 1;
            for(k = 1; k <= n; k++)//更新最短路
            { 
                if(vis[k] == 0 && map[u][k] < INF && dist[k] > dist[u] + map[u][k])
                { 
                    dist[k] = dist[u] + map[u][k];
                }
            }
        }
    }

## **2、Bellman-Ford算法** ##

**转发链接：https://blog.csdn.net/qq\_40984919/article/details/80489441**

**适用条件&范围：**

单源最短路径(从源点s到其它所有顶点v);

有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);

边权可正可负(如有负权回路输出错误提示);

**Bellman-Ford算法的流程如下：**

给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，数组Distant\[i\]记录从源点s到顶点i的路径长度，初始化数组Distant\[n\]为, Distant\[s\]为0；

以下操作循环执行至多n-1次，n为顶点数：

对于每一条边e(u, v)，如果Distant\[u\] + w(u, v) < Distant\[v\]，则另Distant\[v\] = Distant\[u\]+w(u, v)。w(u, v)为边e(u,v)的权值；

若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

**为了检测图中是否存在负环路**，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant\[u\] + w(u, v) < Distant\[v\]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant\[n\]中记录的就是源点s到各顶点的最短路径长度。

**可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V\*E).**

**Bellman－Ford算法可以大致分为三个部分**

第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。

第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。

第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：  
d（v） > d (u) + w(u,v)；则返回false，表示途中存在从源点可达的权为负的回路。

之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。

**只求最短路的代码：**

#include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    
    int n,m,i,j;
    int check;
    
    struct node
    { 
        int u,v,w;
    } a[5000010];
    
    int dis[3000000],top;
    
    void add(int u,int v,int w)
    { 
        a[top].u=u;
        a[top].v=v;
        a[top].w=w;
        top++;
    }
    
    void Bellman(int s,int e)
    { 
        memset(dis,inf,sizeof(dis));
        dis[s]=0;
        for(i=1; i<n; i++)
        { 
            check=0;
            for(j=1; j<top; j++)
            { 
                if(dis[a[j].v] > dis[a[j].u]+a[j].w)
                { 
                    dis[a[j].v] = dis[a[j].u]+a[j].w;
                    check=1;
                }
            }
            if(check==0)   break;
        }
        printf("%d\n",dis[e]);
    }

**求最短路及判断是否有负权回路**

#include<iostream> 
    #include<cstdio> 
    using namespace std;  
      
    #define MAX 0x3f3f3f3f 
    #define N 1010 
    int nodenum, edgenum, original; //点，边，起点 
      
    typedef struct Edge //边 
    {   
        int u, v;  
        int cost;  
    }Edge;  
      
    Edge edge[N];  
    int dis[N], pre[N];  
      
    bool Bellman_Ford()  
    {   
        for(int i = 1; i <= nodenum; ++i) //初始化 
            dis[i] = (i == original ? 0 : MAX);  
        for(int i = 1; i <= nodenum - 1; ++i)  
            for(int j = 1; j <= edgenum; ++j)  
                if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~） 
                {   
                    dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;  
                    pre[edge[j].v] = edge[j].u;  
                }  
                bool flag = 1; //判断是否含有负权回路 
                for(int i = 1; i <= edgenum; ++i)  
                    if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)  
                    {   
                        flag = 0;  
                        break;  
                    }  
                    return flag;  
    }

## **3、Floyd算法** ##

**动态规划思想**

**mp\[ \]\[ \]数组的初始化**

for(i=1; i<=n; i++)
    { 
        for(j=1; j<=n; j++)
        { 
            if(i==j)
                mp[i][j]=0;
            else
                mp[i][j]=INF;
        }
    }
    for(i=0; i<m; i++)
    { 
        scanf("%d %d %d",&a,&b,&c);
        if(c<mp[a][b])
        { 
            mp[a][b]=c;
            mp[b][a]=c;
        }
    }

void Flord()
    { 
        int i,j,k;
        for(k=1;k<=N;k++)
        { 
            for(i=1;i<=N;i++)
            { 
                for(j=1;j<=N;j++)
                { 
                    mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
                }
            }
        }
    }

## **4、SPFA算法** ##

**参考链接：** https://www.cnblogs.com/xzxl/p/7246918.html

SPFA算法与Bellman-Ford算法相似，但是SPFA比Bellman-Ford算法多了一个队列优化；  
**算法描述**

算法特点：在 Bellman-ford 算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。

时间复杂度：O（mn）

关键词：初始化 松弛操作 队列

主要变量如下：

int n　　　 表示有n个点，从1~n标号

int s,t 　　　 s为源点，t为终点

int dis\[N\]　 dis\[i\]表示源点s到点i的最短路径

int pre\[N\]　 记录路径，pre\[i\]表示i的前驱结点

bool vis\[N\] vis\[i\]=true表示点i在队列中

queue q 队列，在整个算法中有顶点入队了要记得标记vis数组，有顶点出队了记得消除那个标记

【初始化】

dis数组全部赋值为INF，pre数组全部赋值为-1（表示还不知道前驱），

dis\[s\] = 0 表示源点不要求最短路径（或者最短路径就是0）。

【队列+松弛操作】

读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d\[v\]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队，这样不断从队列中取出顶点来进行松弛操作。

以此循环，直到队空为止就完成了单源最短路的求解。

【算法过程】

设立一个队列用来保存待优化的顶点，优化时每次取出队首顶点 u，并且用 u 点当前的最短路径估计值dis\[u\]对与 u 点邻接的顶点 v 进行松弛操作，如果 v 点的最短路径估计值dis\[v\]可以更小，且 v 点不在当前的队列中，就将 v 点放入队尾。这样不断从队列中取出顶点来进行松弛操作，直至队列空为止。

【检测负权回路】

方法：如果某个点进入队列的次数大于等于 n，则存在负权回路，其中 n 为图的顶点数。

**说明：SPFA无法处理带负环的图。**

void SPFA(int s,int e)
    { 
        int i;
        queue<int>q;
        memset(vis,0,sizeof(vis));
        for(i=1;i<=n;i++)
        { 
            dis[i] = inf;
        }
        dis[s] = 0;//表示到点到某点的最短路径数组
        vis[s] = 1;//表示该点是否已经在队列中
        q.push(s);
        while(!q.empty())
        { 
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for(i=head[u];i!=-1;i = edge[i].next)
            { 
                int v = edge[i].v;
                if(dis[v]>dis[u]+edge[i].w)
                { 
                    dis[v] = dis[u]+edge[i].w;
                    if(vis[v]==0)
                    { 
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
    }