问题提出：给出一张图，上面有一些点，点与点之间有边相连，要求从起点出发，到达终点所需要花费的最短路程。

输入输出格式如下：

第一行输入两个整数n，m。

接下来的m行，每行输入三个数字u，v，w。

表示在u到v之间存在一条无向边边，边的权值为w。

每次答案输出一个数字，表示从一号顶点出发，走到n号顶点的最短路径。如果不存在则输出-1.

由于有向图和无向图的做法相似，本文提到如无特别标注均为无向图。

input

3 3

1 2 2

2 3 3

3 1 1

output

1

目录

一、Dijkstra算法（单源最短路）

 二、Dijkstra算法的堆优化

三、Bellman_Ford算法

四、SPFA算法（Bellman_Ford的队列优化）

五、Floyd算法（多源最短路）

可以将此类问题分为单源和多源。单源意为从一个点出发，求这个点到所有顶点的最短路。多源则可以求出任意两个顶点的最短路。我们先从单源开始讨论。

一、Dijkstra算法（单源最短路)

Dijkstra算法是基于贪心策略的，算法的大致思想如下：先定义一个dist数组储存起点到每一个点（目标点用数组的下标来表示）的最短路径，dist的每一项初始值为无穷大，意为着在不知道边的情况下起点到每一个点都是不可达的。开始将起点加入集合并标记，尝试更新与起点相连的顶点的距离，更新之后再从dist数组中取与起点最近的点加入集合并标记，用这个点继续尝试更新起点到其他点的距离。算法的时间复杂度为：

C++实现如下：

#include <bits/stdc++.h>
using namespace std;
const int mx=205;
int n,m,mp[mx][mx],dis[mx],vis[mx];
void Dijkstra(){
    for(int i=1;i<=n;i++)
        if(mp[1][i])
            dis[i]=mp[1][i];
    dis[1]=0;
    vis[1]=1;
    for(int i=1;i<=n;i++){
        int k,tmp=0x3f3f;
        for(int j=1;j<=n;j++)  //每次取出离起点最近的点编号和距离
            if(!vis[j]&&dis[j]<tmp)
                k=j,tmp=dis[j];
        vis[k]=1;
        for(int j=1;j<=n;j++)  //尝试更新
            if(!vis[j]&&dis[j]>dis[k]+mp[k][j])
                dis[j]=dis[k]+mp[k][j];
    }
}
int main()
{
    while(cin>>n>>m&&n){
        memset(dis,0x3f3f,sizeof dis);
        memset(vis,0,sizeof vis);
        memset(mp,0x3f3f,sizeof mp);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            mp[a][b]=mp[b][a]=min(mp[a][b],c);  //加边去重边
        }
        Dijkstra();
        cout<<dis[n]<<endl;
    }
}

 我想可能有的同学会有疑问：为什么Dijkstra的贪心策略是正确的呢？我在此可以提出一个非常简单的理解。

 在上面的图中，从A到C有两种选择，一种是直接到C，一种是经过一个（或者多个）点到C。假设我们现在认为A到C的距离是最短的，打算将他加入最短路径了（即把这个点确定下来，不再更新），那么你是否有过一个疑问，为什么不会出现后面再找出一条通过其他点的边，使得A经过点B到达C的距离更小呢？这显然是不可能的。因为我们在确定下这条边的时候所采用的策略就是寻找离A（起点）最近的点。A到达B的距离必然大于A到达C的距离，因此在不出现负权边的情况下AC显然小于AB+BC。这点同时也解释了Dijkstra为什么不能处理负权边，因为按照Dijkstra的策略算法在处理到C是离起点最近就会将AC这条边固定下来。假设BC<0，则AC是有可能大于AB+BC的。

 二、Dijkstra算法的堆优化

上面的算法不仅思想容易理解，实现也非常简单。整个算法是 量级的当n接近1e5时，算法就会超时。我们每次在取边的时候都必须使用一个循环，这个开销是可以优化的。我们可以用堆来维护取到起点最短距离的点这个过程，只要每一次取走堆顶就可以了。用邻接表来代替邻接矩阵，进一步优化算法。算法的时间复杂度为：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int mx=1e6+5;
int n,m,idx,e[mx],w[mx],ne[mx],h[mx],dis[mx],vis[mx];
void add(int a,int b,int c){  //邻接表加边
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int Dijkstra(){
    dis[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;  //建堆
    heap.push({0,1});  //first表示到起点的距离 second表示点的编号
    while(heap.size()){
        PII t=heap.top();
        heap.pop();
        int v=t.second,d=t.first;
        if(vis[v])  continue;  //当前点已经被标记表示已经用这个点更新过到其他点的距离
        vis[v]=1;
        for(int i=h[v];~i;i=ne[i]){
            int j=e[i];
            if(dis[j]>d+w[i]){
                dis[j]=d+w[i];
                heap.push({dis[j],j});
            }
        }
    }
    return dis[n]==0x3f3f3f?-1:dis[n];
}
int main()
{
    while(cin>>n>>m&&n){
        memset(dis,0x3f3f3f,sizeof dis);
        memset(h,-1,sizeof h);
        memset(vis,0,sizeof vis);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c),add(b,a,c);
        }
        cout<<Dijkstra()<<endl;
    }
}

 Dijkstra固然简单易写好理解，但是在遇到负权边时却无法处理，因为Dijkstra只对每一条边放松一次。在处理负权边时，如果负权边靠后才被用于更新到其他节点的距离而被更新的点又正好被标记过已经计入最短路径的话，更新便会失效（表述可能不准确，欢迎指正）。因此当我们在处理有负权边的时候，不能使用Dijkstra算法（这个其实上面已经解释过了，好好想一想，你会明白的）。

该算法的思想是：利用两层循环，内层循环表示枚举所有的边并对所有的边进行放松，外层循环表示使用几条边（外层循环每执行一次，内层循环就会放松一次所有的边，当外层循环执行的时候随着内层循环的进行被成功放松的边就会越来越多，找最短路径使用放松过的边也就越多）。 算法的时间复杂度为：

C++实现如下：

#include <bits/stdc++.h>
using namespace std;
const int mx=1e5+5;
int n,m,dist[505],bck[505];
struct edge{
    int a,b,w;
};
vector<edge> e;
int Bellmanford(){
    dist[1]=0;
    for(int i=0;i<n-1;i++){  //算法主体
        memcpy(bck,dist,sizeof dist);  //此处是一个备份  用于检测是否已经找到所有的最短路
        for(int j=0;j<e.size();j++)
            if(dist[e[j].b]>dist[e[j].a]+e[j].w)
                dist[e[j].b]=dist[e[j].a]+e[j].w;
        int flag=1;
        for(int j=0;j<e.size();j++)  //如果再次放松后的结果与上一次无异
            if(dist[j]!=bck[j]){     //则说明所有最短路都已经被找到
                flag=0;
                break;
            }
        if(flag)
            break;
    }
    return dist[n];
}
int main()
{
    while(cin>>n>>m&&n){
        memset(dist,0x3f3f,sizeof dist);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            e.push_back({a,b,c});
            e.push_back({b,a,c});
        }
        cout<<Bellmanford()<<endl;
        e.clear();
    }
}

在上述的Bellman_Ford算法中，我们已经使用备份的方式让算法能够在找到所有最短路后及时跳出，但是有一些边在放松的过程中依然“不为所动”因为他们本身就已经是最短路径了，只是还在等待剩余的最短路径被找到。基于此，我们还可以进一步优化算法，SPFA算法便出现了。

由于Bellman_Ford算法的特质（其实指的就是两层循环松弛所有边），使得该算法在有边数限制的最短路问题中具有无可替代的作用。

一个例题：acwing853. 有边数限制的最短路

C++ Code：

#include <bits/stdc++.h>
using namespace std;
const int mx=1e5+5;
int n,m,k,dist[505],bck[505];
struct edge{
    int a,b,w;
};
vector<edge> e;
int Bellmanford(){
    dist[1]=0;
    for(int i=0;i<k;i++){
        memcpy(bck,dist,sizeof dist);
        for(int j=0;j<e.size();j++)
            dist[e[j].b]=min(dist[e[j].b],bck[e[j].a]+e[j].w);
    }
    return dist[n]>0x3f3f3f/2?0x3f3f3f:dist[n];  //这里写成这样的原因是                                                 
}                                                //为了抵消一些小的负权边对于备份的影响
int main()
{
    while(cin>>n>>m>>k){
        memset(dist,0x3f3f3f,sizeof dist);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            e.push_back({a,b,c});
        }
        int t=Bellmanford();
        if(t==0x3f3f3f)
            puts("impossible");
        else
            cout<<t<<endl;
        e.clear();
    }
}

四、SPFA算法（Bellman_Ford的队列优化）

从标题你已经看见了，我们在对边进行放松的时候，完全没有必要盲目的对每一条边都放松，当我们放松成功一条边后必然有一个点的距离发生了改变，我们只要顺藤摸瓜一般对这个点相邻的各个点的距离进行修改即可。我们可以用一个队列来维护这些点，大致的思想如下我们每次都取出队头的点，尝试对与该点相邻的每一条出边都进行放松，如果放松成功并且与该边相邻的另一顶点并未在队列中，则将该点入队，重复操作直到队空。算法的时间复杂度为：(一般)  (最坏)。有些题目会卡SPFA，正权图乖乖Dijkstra不会错。

图示和算法演示详细操作可以看这位大佬的这篇博客。

C++实现如下：

#include <bits/stdc++.h>
using namespace std;
const int mx=1e5+5;
int n,m,k,dist[505],vis[505];
int e[mx],w[mx],h[mx],ne[mx],idx;
queue<int> q;
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa(){
    dist[1]=0;
    vis[1]=1;
    q.push(1);  //起点入队
    while(q.size()){
        int t=q.front();
        q.pop();
        vis[t]=0;
        for(int i=h[t];~i;i=ne[i]){  //relax队头元素相连的边
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!vis[j])
                    q.push(j),vis[j]=1;
            }
        }
    }
    return dist[n]==0x3f3f3f?-1:dist[n];
}
int main()
{
    while(cin>>n>>m&&n){
        memset(dist,0x3f3f3f,sizeof dist);
        memset(vis,0,sizeof vis);
        memset(h,-1,sizeof h);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c),add(b,a,c);
        }
        cout<<spfa()<<endl;
    }
}

这里我们还可以引入一个常用的优化，即SLF（Small Label First）优化 ：

意义是对要加入队列的点 u，如果 dist[u] 小于队头元素 v 的 dist[v]，将其插入到队头，否则插入到队尾。

关键代码如下：

bool spfa(int s){
    deque<int> q;
    hd[s]=0;  //这里hd代表距离
    vis[s]=1;
    cnt[s]++;
    q.push_back(s);
    while(q.size()){
        int u=q.front();
        q.pop_front();
        vis[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int j=e[i];
            if(hd[j]>hd[u]+w[i]){
                hd[j]=hd[u]+w[i];
                if(!vis[j]){
                    if(q.size()&&hd[j]>hd[q.front()])  //SLF优化
                        q.push_back(j);
                    else
                        q.push_front(j);
                    vis[j]=1,cnt[j]++;
                    if(cnt[j]>n)  return false;  //判环
                }
            }
        }
    }
    return true;
}

至此，单源最短路的问题就结束了，我们讨论多源最短路。有学弟学妹问我可以用单源最短路解决多源最短路的问题吗？答案是当然可以，换个接口，函数内传入一个参数代表起点start就可以了。但是 ！！根本没必要！！因为无论是码量还是复杂程度都不如使用多源最短路的Floyd算法香。

五、Floyd算法（多源最短路）

Floyd算法是一种基于动态规划的多源最短路算法，它的核心代码非常简单只有三个循环，论码量属于最小的多源最短路算法（因为我也只会这个555确信）。它的核心思想是，中层循环i代表的顶点，到达最内层循环j代表的顶点的路上借助了最外层循环k所代表的顶点。

C++实现如下：

#include <bits/stdc++.h>
using namespace std;
const int mx=205;
int n,m,mp[mx][mx];
int main()
{
    while(cin>>n>>m&&n&&m){
      memset(mp,0x3f3f3f,sizeof mp);
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            mp[a][b]=mp[b][a]=min(c,mp[a][b]);
        }
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(mp[i][j]>mp[i][k]+mp[k][j])
                        mp[j][i]=mp[i][j]=mp[i][k]+mp[k][j];
                }
            }
        }
        cout<<mp[1][n]<<endl;
    }
}

博客到此结束，如有问题欢迎各位大佬指正。我又回来了，给大家带来一种船新的多源最短路算法。

六、Johnson算法（稀疏图）

 Johnson 和 Floyd 一样，是一种能求出无负环图上任意两点间最短路径的算法。该算法在 1977 年由 Donald B. Johnson 提出。任意两点间的最短路可以通过枚举起点，跑n次 Bellman-Ford 算法解决，时间复杂度是的，也可以直接用 Floyd 算法解决，时间复杂度为。如果采用Dijkstra算法枚举起点则比Bellman_Ford更优，为。但是Dijkstra算法无法处理负权图。基于此，我们可以对图的边权稍微进行一下处理，使得算法能够正常运行起来。

一个比较容易想到的思想就是：给每条边加上一个数x，使得所有边为正权，在进行Dijkstra的时候把跑的边数k统计起来，最后再减去kx。但是这种方法是错误的。为什么？考虑下图：

 显然：1到2的最短路径为1->5->3->2。长度为-2。

如果我们给每一条边都加上6（把0权的边也消掉更有普适性）。

那么最短路径显然变成了1->4->2。造成这样的原因就在于从一个顶点到另一个顶点所经过的边数不同，而为了使得每一条边都变为正权添加的数字x较大，在经过不同边数的路径中，对其所造成的影响也不同。 正确的策略如下：

我们新建一个虚拟节点（在这里我们就设它的编号为0）。从这个点向其他所有点连一条边权为0的边。接下来用Bellman-Ford/SPFA算法求出从0号点到其他所有点的最短路，记为。

假如存在一条从u点到v点，边权为w的边，则我们将该边的边权重新设置为。这种做法可以保证更改后的每条边权为正，也很容易证明，可以自己尝试一下。

接下来以每个点为起点，跑n轮Dijkstra算法即可求出任意两点间的最短路了。

容易看出，该算法的时间复杂度是。吐槽：码量上还不如n遍Bellman_Ford呢。

C++ Code：  以P5905 【模板】Johnson 全源最短路为例

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int mx=1e4+10,INF=1e9;
int n,m,cnt[mx],vis[mx];
int e[mx],w[mx],ne[mx],h[mx],idx;
long long hd[mx],dist[mx];
inline void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(int s){
    deque<int> q;
    hd[s]=0;
    vis[s]=1;
    cnt[s]++;
    q.push_back(s);
    while(q.size()){
        int u=q.front();
        q.pop_front();
        vis[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int j=e[i];
            if(hd[j]>hd[u]+w[i]){
                hd[j]=hd[u]+w[i];
                if(!vis[j]){
                    if(q.size()&&hd[j]>hd[q.front()])  //SLF优化
                        q.push_back(j);
                    else
                        q.push_front(j);
                    vis[j]=1,cnt[j]++;
                    if(cnt[j]>n)  return false;  //判环
                }
            }
        }
    }
    return true;
}
void dijkstra(int s){
    fill(dist,dist+mx,INF);
    fill(vis,vis+mx,0);
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    dist[s]=0;
    heap.push({0,s});
    while(heap.size()){
        int u=heap.top().second;
        heap.pop();
        if(vis[u])  continue;
        vis[u]=1;
        for(int i=h[u];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[u]+w[i]){
                dist[j]=dist[u]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}
signed main()
{
    memset(h,-1,sizeof h);
    memset(hd,0x3f,sizeof hd);
    cin>>n>>m;
    for(int i=0,a,b,c;i<m;i++){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    for(int i=1;i<=n;i++)
        add(0,i,0);
    if(!spfa(0)){
        cout<<-1<<endl;
        exit(0);
    }
    for(int i=1;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
            w[j]+=hd[i]-hd[e[j]];
    for(int i=1;i<=n;i++){
        dijkstra(i);
        long long ans=0;
        for(int j=1;j<=n;j++){
            if(dist[j]==INF)
                ans+=j*INF;
            else
                ans+=j*(dist[j]+hd[j]-hd[i]);
        }
        cout<<ans<<endl;
    }
}

完结撒花~