最短路径四大算法「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

熟悉的最短路算法就几种：bellman-ford，dijkstra，spfa，floyd。
bellman-ford可以用于边权为负的图中，图里有负环也可以，如果有负环，算法会检测出负环。
时间复杂度O（VE）;
dijkstra只能用于边权都为正的图中。
时间复杂度O（n2）；
spfa是个bellman-ford的优化算法，本质是bellman-ford，所以适用性和bellman-ford一样。（用队列和邻接表优化）。
时间复杂度O（KE）;
floyd可以用于有负权的图中，即使有负环，算法也可以检测出来,可以求任意点的最短路径，有向图和无向图的最小环和最大环。
时间复杂度O（n3）；
任何题目中都要注意的有四点事项：图是有向图还是无向图、是否有负权边，是否有重边，顶点到自身的可达性。
1、Dijkstra（单源点最短路）
这个算法只能计算单元最短路，而且不能计算负权值，这个算法是贪心的思想， dis数组用来储存起始点到其他点的最短路，但开始时却是存的起始点到其他点的初始路程。通过n-1遍的遍历找最短。每次在剩余节点中找dist数组中的值最小的，加入到s数组中，并且把剩余节点的dist数组更新。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 0x3f3f3f3f;
const int p = 1005;
int a[p][p];//存放点与点的距离
int dist[p];//源点到各个点的最短距离
int pre[p];//计算过的点
int s[p];//判断是否已经加入pre,是否已访问
int n,m;
void Dijkstra(int v)
{
    int i,j;
    for(i = 0;i < n;++i)
    {
        if(i != v)
        {
            dist[i] = a[v][i];
        }
        s[i] = false;
    }
    s[v] = true;
    dist[v] = 0;
    pre[0]=v;
    //对各个数组进行初始化
    for(i = 0;i < n;++i)
    {
        int minset = MAXN;
        int u = v;
         for(j = 0; j < n;++j)
         {
             if(!s[j] && dist[j] < minset)
             //找到剩余节点中最小的节点
             {
                 u = j;
                 minset = dist[u];
             }
         }
         s[u] = true;
         //将节点标记为以访问，相当于加入s数组中
         for(j = 0;j < n;++j)
         {
             if(!s[j] && a[u][j] < MAXN)
             //a[u][j] < MAXN指更新u的可达点
             {
                 if(dist[u] + a[u][j] < dist[j])
                 {
                     dist[j] = dist[u] + a[u][j];
                     pre[j] = u;
                     //储存得出最短路径的前一个节点，用于路径还原
                 }
             }
         }
    }
}
int main()
{
    int t;
    cin>>t;
    while(~scanf("%d %d",&n,&m))
    {
        memset(a,MAXN,sizeof(a));
        memset(dist,MAXN,sizeof(dist));
        int i,j;
        for(i = 0;i < m;++i)
        {
            int x,y,d;
            scanf("%d %d %d",&x,&y,&d);
            a[x-1][y-1]=d;
            a[y-1][x-1]=d;
        }
        //int v;
        //scanf("%d",&v);
        Dijkstra(0);
        for(int i = 0;i < n;++i)
        {
            printf("%d ",dist[i]);
        }
        printf("\n");
        /*for(int i = 0;i < n;++i) { printf("%d ",s[i]); } printf("\n"); for(int i = 0;i < n;++i) { printf("%d ",pre[i]); } printf("\n");*/
    }
    return 0;
}

Floyd:
floyd算法是非常强大的，可以处理不少问题，复杂度是O（n^3）的，下面解析一下这个算法
不少人可能刚接触floyd的时候非常容易把它写错，错误的写法就是三层循环的从外到内的变量分别为i，j，k，正确的写法应该是k，i，j。写错的原因是不理解floyd算法造成的，那么为什么从顺序是k，i，j呢？

其实floyd的算法本质是个动态规划！dp[k][i][j]代表i到j的中间节点（不包括i和j）都在区间[1，k]时，i到j的最短路。算法的最外层循环是个从小到大枚举k的过程，当最外层刚刚进入第k次循环的时候，我们已经得到了所有点对的dp[k-1][][]的值，也就是所有点对（i，j）的i到j的中间节点都在[1，k-1]区间的i到j的最短路。那么对任意的点对（i，j），如果他俩的最短路经过k点，则dp[k][i][j]=dp[k-1][i][k]+dp[k-1][k][j]；如果不经过k点，则dp[k][i][j]=dp[k-1][i][j]。所以当我们求dp[k][][]的时候，要保证所有的dp[i-1][][]都求出来了，因此，最外层循环是k。
每一层都是有上一层决定，不会受这一层影响，所以可以利用滚动数组优化内存空间，将k去除掉

任意节点i到j的最短路径不外乎两种可能：1、直接从i到j；2、从i经过若干个节点k到j。Dis（i，j）表示节点i到j最短路径的距离，对于每一个节点k，检查Dis（i，k）+Dis（k，j）小于Dis(i,j),如果成立，Dis（i，j） = Dis（i，k）+Dis（k，j）；遍历每个k，每次更新的是除第k行和第k列的数。（十字交叉法，可百度）。

floyd能做很多事情，下面简单说两个，求有向图的最小环或者最大环（顶点数>=2），求无向图的最小环（顶点数>=3）。

先说求有向图最小环（最大环略）。有两种方法可以求，一种是设定g[i][i]为无穷大，这样最后找所有的g[i][i]里的最小值就行；另一种是正常做floyd，然后对每个点对（i，j），求g[i][j]+dp[n][j][i]的最小值，这样的原理是最小环如果存在的话，那么可以枚举一个这个环里的边i->j，那么包含这条边的最小的环一定是i->j和dp[n][j][i]构成的最短路。

无向图的最小环做法和有向图不一样，是因为无向边可能会被用两次导致出错，举例说就是：枚举了一条边i->j，然后其与dp[n][j][i]的和作为一个结果，但是如果j到i的最短路就是边j->i的话，那么我们找的环其实只是一条边而已，这样的结果显然是错误的。正确的做法是先判断最小环再更新最短路。（为什么？）
因为会出现重边的现象，所以一个环一定至少有三个点，所以每次先判断最小环，因为k必须是未用过的，此时的dist[i][j]是遍历了k-1次的最短路，用完判断了再去更新k对应的最短路。每次比较dist[i][j]+
g[i][k]+g[k][j]的最小值。k—>i————>j—->k;这样一直保证环是三个点。

hdu1599（用Floyd求无向图的最小环）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100005;
const int p = 105;
int dist[p][p];
int mp[p][p];
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        int i,j,k;
        for(i = 0;i < n;++i)
        {
            for(j = 0;j < n;++j)
            {
                dist[i][j] = MAXN;
                mp[i][j] = MAXN;
            }
        }
        for(i = 0;i < m;++i)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            if(c < mp[a-1][b-1])
                   dist[a-1][b-1]=dist[b-1][a-1]=mp[b-1][a-1]=mp[a-1][b-1]=c;
        }
        int ans = MAXN;
        for(k = 0;k < n;++k)
        {
            for(i = 0;i < n;++i)
            {
                for(j = i+1;j < n;++j)
                //这里用i+1，防止i，j是不同的两个点
                {
                    if(ans > dist[i][j] + mp[i][k] + mp[k][j])
                    {
                        ans = dist[i][j] + mp[i][k] + mp[k][j];
                    }
                }
            }
            for(i = 0;i < n;++i)
            {
                for(j = 0;j < n;++j)
                {
                    if(dist[i][j] > dist[i][k] + dist[k][j])
                    {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        if(ans == MAXN)
            printf("It's impossible.\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}

Floyd的模板：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 0x3f3f3f3f;
const int p = 1005;
int dist[p][p];
int path[p][p];
int mp[p][p];
int n,m;
int Floyd()
{
    int i,j,k;
    for(i = 0;i < n;++i)
    {
        for(j = 0;j < n;++j)
        {
            dist[i][i]=0;
            mp[i][i]=0;
        }
    }
    int ans = MAXN;
    for(k = 0;k < n;++k){
    for(i = 0;i < n;++i)
    {
        for(j = 0;j < n;++j)
        {
            if(dist[i][k] + dist[k][j] < dist[i][j])
            {
                dist[i][j] = dist[i][k] + dist[k][j];
                path[i][j] = k;
            }
        }
    }
    }
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int i,j;
        memset(path,-1,sizeof(path));
        memset(dist,MAXN,sizeof(dist));
        memset(mp,MAXN,sizeof(mp));
        scanf("%d %d",&n,&m);
        for(int i = 0;i < m;++i)
        {
            int x,y,d;
            scanf("%d %d %d",&x,&y,&d);
            dist[x][y]=d;
            dist[y][x]=d;
            mp[x][y]=d;
            mp[y][x]=d;
        }
        printf("%d\n",Floyd());
        for(i = 0;i < n;++i)
        {
            for(j = 0;j < n;++j)
            {
                printf("%d ",dist[i][j]);
            }
            cout<<endl;
        }
        for(i = 0;i < n;++i)
        {
            for(j = 0;j < n;++j)
            {
                printf("%d ",path[i][j]);
            }
            cout<<endl;
        }
    }
    return 0;
}

Bellman-Ford：
适用范围：1、单源最短路径（从源点到其他所有点v）；
2、有向图&无向图；
3、边权可正可负
4、差分约束系统
图G(v,e),源点s，数组Distant[i]记录了从源点s到顶点i的路径长度，循环执行至多n-1次，n为顶点数。
对每一条边e（u，v），如果Distant[u]+w[u,v]小于Distant[v],则Distant[v] = Distant[u]+w(u,v);
每一次循环都会至少更新一个点，所以才会出现至多循环n-1次，一次更新是指用所有节点进行一次松弛操作，（为什么会出现循环一次都能至少确定一个节点的最短距离？）
因为：1、将所有节点分为两类：已知最短距离的节点和剩余节点。
2、这两类节点满足这样的性质：已知最短距离的节点的最短距离值都比剩余节点的最短路值小。
3、易知到剩余节点的路径一定会经过已知节点。
4、而从已知节点连到剩余节点的所以边中的最小的那个边，这条边所更新后的剩余节点就一定是确定的最短距离，从而多找到了一个能确定最短距离的节点（不用知道它是哪个节点）。

实现过程的三步：1、初始化所有的点，每一个点保存一个值，表示源点到这个点的距离其他点的值设为无穷大。
2、进行循环，从1到n-1，进行松弛计算。
3、遍历所有边，如果的d[v]大于d[u]+w(u,v)存在，则有从源点可达的权为负的回路。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 0x3f3f3f3f;
const int p = 100005;
typedef struct Graph{
   int u,v,cost;
};
//有向图
Graph edge[p];//边表
int pre[p];
int dis[p];
int n,m,v;//点数，边数，源点
bool BellmanFloyd()
{
    int i,j;
    for(i = 1;i <= n;++i)//最多进行n-1次更新
    {
        for(j = 0;j < m;++j)//每次遍历一下边表，至少找出一个点的最短路径
        {
            if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cost)
            {
                dis[edge[j].v]=dis[edge[j].u]+edge[j].cost;
            }
        }
    }
    bool flag = true;
    for(i = 0;i < m;++i)//判断负环
    {
        if(dis[edge[i].v]>dis[edge[i].u]+edge[i].cost)
        {
            flag = false;
            break;
        }
    }
    return flag;
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        int i,j;
        memset(dis,MAXN,sizeof(dis));
        memset(pre,-1,sizeof(pre));
        for(i = 0;i < m;++i)
        {
            scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].cost);
        }
        dis[1] = 0;
        pre[1] = 1;
        BellmanFloyd();
            for(i = 1;i <= n;++i)
            {
                printf("%d ",dis[i]);
            }
            printf("\n");
    }
    return 0;
}

介绍SPFA之前先介绍一个图的存储方式：邻接表（可以用来优化算法）
可以用数组实现，因为本人不喜欢用指针实现，所以也没尝试。
对于图来说，邻接矩阵是不错的一种图存储结构，但是我们也发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式：邻接表（Adjacency List），即数组与链表相结合的存储方法。
邻接表的处理方法是这样的。
1、图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2、图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。

用数组实现

next[i]存储的是“编号为i的边”的“前一条边”的编号。
可通过next找到以某一个顶点为起始点的所有边。

SPFA是一种求单源最短路的算法（Bellman-ford的优化版）
算法中需要用到的主要变量
int n; //表示n个点，从1到n标号
int s,t; //s为源点，t为终点
int d[N]; //d[i]表示源点s到点i的最短路
int p[N]; //记录路径（或者说记录前驱）
queue q; //一个队列，用STL实现，当然可有手打队列，无所谓
bool vis[N]; //vis[i]=1表示点i在队列中 vis[i]=0表示不在队列中
几乎所有的最短路算法其步骤都可以分为两步
1.初始化
2.松弛操作
初始化： d数组全部赋值为INF（无穷大）；p数组全部赋值为s（即源点），或者赋值为-1，表示还没有知道前驱点， 然后d[s]=0; 表示源点不用求最短路径，或者说最短路就是0。将源点入队；（另外记住在整个算法中有顶点入队了要记得标记vis数组，有顶点出队了记得消除那个标记）

队列+松弛操作
读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队
以此循环，直到队空为止就完成了单源最短路的求解

SPFA可以处理负权边
定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。
证明：
每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）
期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。
判断有无负环：
如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）

算法思想：我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MAXN = 20005;
const int MINX = 1005;
int u[MAXN];
int v[MAXN];
int w[MAXN];
int first[MINX];
int ne[MAXN];
int d[MINX];
bool vis[MINX];
int p[MINX];
queue<int>que;
void spfa_bfs()
{
    int i,j;
    while(!que.empty())
    {
        int k = que.front();
        que.pop();
        vis[k] = 0;
        for(int x = first[k];x != -1;x = ne[x])
        {
            int y = v[x];
            if(d[y] > d[k] + w[x])
            {
                d[y] = d[k] + w[x];
                p[y] = x;
                if(!vis[y]){
                    vis[y] = 1;
                    que.push(y);
                }
            }
        }
    }
}
int main()
{
    int n,m,s,t;
    while(~scanf("%d %d %d",&n,&m,&s))
    {
        int x,y,z;
        int i,j;
        memset(ne,-1,sizeof(ne));
        memset(first,-1,sizeof(first));
        memset(vis,0,sizeof(vis));
        memset(d,inf,sizeof(d));
        memset(p,-1,sizeof(p));
        d[s] = 0;
        vis[s] = 1;
        p[s] = s;
        que.push(s);
        for(i = 1;i <= m;++i)
        {
            scanf("%d %d %d",&x,&y,&z);
            u[i] = y;
            v[i] = x;
            w[i] = z;
            if(first[y] == -1){
                first[y] = i;
            }
            else
            {
                ne[i] = first[y];
                first[y] = i;
            }
        }
        spfa_bfs();
        /*for(i = 1;i <= m;++i) { printf("%d %d %d %d %d\n",u[i],v[i],w[i],first[i],ne[i]); } for(i = 1;i <= n;++i) { printf("%d ",d[i]); } cout<<endl;*/
        scanf("%d",&t);
        int ptr;
        int mx = inf;
        for(j = 0;j < t;++j)
        {
            scanf("%d",&ptr);
            mx = (mx > d[ptr])?d[ptr]:mx;
        }
        if(mx == inf)
            printf("-1\n");
        else
            printf("%d\n",mx);
    }
    return 0;
}