算法最短路问题（从入门到精通）

原创

潋湄

修改于 2024-12-11 09:32:08

11700

代码可运行

运行总次数：0

代码可运行

推荐文章：https://cloud.tencent.com/developer/article/2474511?policyId=20240001&traceId=01jesmy38j9nrp142z5gzy1vqt 本文从LLM视角详细介绍了当下我们应该如何利用Java开发一个优质的AIGC应用，具有广泛应用意义

在图论算法中，最短路问题是相当大的一个范畴，而且最短路问题考的形式很多，但是万变不离其宗，核心就是要掌握最短路问题的每个算法对应原理，这样就能以不变应万变。

本篇文章先介绍了各个最短路算法的模板，之后通过实际题目展示最短路算法的解决技巧与原理运用，希望读者能够看到最后

首先我们看一看最短路问题的大致分类：

最短路算法汇总

其实最短路算法并不难理解，这里先简单讲一下每一个算法原理（详细原理读者可以自行搜索）

原理讲解在代码注释中：

1、Dijsktra算法（朴素版）

#include<iostream>
using namespace std;
#include<cstring>

const int N = 510;//顶点的最大个数
int g[N][N],dist[N];//g存储每条边的权重，dist存储每个点到初始点的距离
bool st[N];//判断一个点是否被添加到最短路集合中
int n,m;//顶点数，边数

int Dijkstra(){//迪杰斯特拉算法，如果有最短距离，返回，如果不连通，返回-1
    memset(dist,0x3f,sizeof(dist));//初始化每一个点的距离
    dist[1]=0;//将计算最短距离的源点距离设置为0
    for(int i=0;i<n;i++){//循环n次,意味着我们要经过不少于n个顶点来更新我们的最短距离
        int t=-1;//储存最短边的序号
        for(int j=1;j<=n;j++)//遍历每个顶点，所以下标从1开始，找到最短的那条边
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
//如果这个点还没有被添加过同时距离最短就用它更新其他所有边的距离
                t=j;

        st[t]=true;//将这个点添加进来
        for(int j=1;j<=n;j++)//用这个点更新其他点的距离
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }

    if(dist[n]==0x3f3f3f3f)return -1;//如果到n的距离是这个，说明两个点之间没有通路
    return dist[n];
}

int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof(g));//初始化各个边的权重，以利于后面的更新每条边权重
    int a,b,c;
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);//因为可能存在重边，所以为了获得最短路，要保留最短的那条边
    }

    printf("%d",Dijkstra());

    return 0;
}

2、Dijsktra算法（堆优化版）【模板】单源最短路径（标准版） - 洛谷

#include<iostream>
using namespace std;
#include<cstring>
#include<queue>

const int N = 1e5+10,M=2*N;
int e[M],ne[M],w[M],h[N],idx;
int dist[N];
bool st[N];
int n,m,s;

//方便后面书写
typedef pair<int,int> PII;

//建图
void add(int a,int b,int c){
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void Dijkstra(){
//初始时先将所有距离设置为正无穷，以利于后面更新距离
	memset(dist,0x3f,sizeof(dist));
//源点距离为0
	dist[s]=0;
//堆优化版Dijsktra算法，按照距离从小到大排序，保证了每次取出的键值对
//是当前距离源点最小且为遍历的点
	priority_queue<PII,vector<PII>,greater<PII> >heap;
//将源点入堆
	heap.push({0,1});
	while(heap.size()){
		PII t=heap.top();
		heap.pop();
		
		int dis=t.first,ver=t.second;
		if(st[ver])continue;
		st[ver]=true;
		
//与朴素版一样，用当前点更新其他点距离并进行更新
		for(int i=h[ver];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]>dis+w[i]){
				dist[j]=dis+w[i];
				heap.push({dist[j],j});
			}
		}
	}
}

int main(){
	cin>>n>>m>>s;
	
	memset(h,-1,sizeof(h));
	while(m--){
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		add(a,b,w);
	}
	
	Dijkstra();
	
	for(int i=1;i<=n;i++)printf("%d ",dist[i]);
	
	return 0;
}

## 3、SPFA算法（大部分求单源最短路会用Dijsktra算法，但是有些题只能用这个，后面会举例子）

int SPFA(){
    memset(dist,0x3f,sizeof(dist));//将所有距离全部初始化为无穷大
    dist[1]=0;//源点距离为0

    queue<int>q;
    q.push(1);//将1节点入队
    st[true];//入队节点st设置为true
    while(q.size()){
        auto t=q.front();
        q.pop();//出对

        st[t]=false;//出队后的顶点在后续有可能还会更新最短距离，所以在这里将这个设置为false
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    st[j]=true;
                    q.push(j);//如果说这个点的距离被更新过同时还没有添加到队列中，就更新这个点的距离同时加入到队列中
                }
            }
        }
    }
    return dist[n];
}

我们在解决实际单源最短路问题会经常使用Dijsktra算法，那么为什么我们还要学习SPFA算法呢，因为如果图中存在负环，我们必须只能使用SPFA算法，如果此时使用Dijsktra算法会陷入死循环，就会导致最后负环上的点到源点距离为负无穷

4、Bellman-Ford算法

#include<iostream>
using namespace std;
#include<cstring>

//可以用来解决k条边限制情况下的最短路问题

const int N = 510,M = 10010;//最大顶点数，边数

struct edge{
    int a,b,w;
}Edge[M];//存储每一条边的信息

int dist[N],backup[N];//每一个点到源点的距离，backup数组存储上一次操作后每一条边的距离，防止发生串联
int n,m,k;//顶点数，边数，最多使用边数

void Bellmac_Ford(){
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;//源点为1，源点的距离为0
    for(int i=0;i<k;i++){//最多使用k条边，外层每循环一次，就会使用一条边
        memcpy(backup,dist,sizeof(dist));//存储一下上一次操作之后的距离，否则会发生串联
        for(int i=0;i<m;i++){//对每一条边更新一次距离
            auto t=Edge[i];
            dist[t.b]=min(dist[t.b],backup[t.a]+t.w);//更新距离，这里一定要使用backup数组，否则前面的边改变会发生串联
        }
    }

    //大于最大值除以2的原因是有可能会加上负权边
    if(dist[n]>0x3f3f3f3f/2)printf("impossible");//如果结果大于一个很大的数字，说明没有通路
    else printf("%d",dist[n]);
}

int main(){
    cin>>n>>m>>k;

    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        Edge[i].a=a,Edge[i].b=b,Edge[i].w=c;
    }

    Bellmac_Ford();

    return 0;
}

5、Floyd算法：【模板】Floyd - 洛谷

#include<iostream>
using namespace std;
#include<cstring>
 
const int N = 110;
int g[N][N];
int n,m;
 
//Floyd算法
void Floyd(){
//每次选取中间点进行距离的更新
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
 
 
int main(){
    scanf("%d%d%d",&n,&m,&k);
 
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=n;i++)g[i][i]=0;//每个点到自己的距离为0
 
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);//可能存在重边，每次读入新边要取边长比较小的那个
    }
 
    Floyd();
 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            printf("%d ",g[i][j]);
        printf("\n");
    }
    return 0;
}

这就是大致的最短路算法，接下来开始讲解最短路算法的一些技巧应用：

最短路算法技巧应用

1、建立虚拟源点：P1137选择最佳线路

https://www.luogu.com.cn/problem/P1137

题意翻译：就是琪琪可以选择家附近的任何一个车站，最后求到达朋友家的最短时间

我们思考，首先琪琪家附近有很多车站可以作为起点，是一个多源最短路问题，但是如果对每个起点进行一遍Dijsktra求解肯定会超时，于是我们思考如何进行优化。

我们发现，琪琪可以从家到任何一个车站，那么我们可以建立一个虚拟源点0号点，将0号点与每一个起点连接一条边权为0的边，这样直接求解距离0号点的单源最短路即可，代码如下：

#include<iostream>
using namespace std;
#include<cstring>
#include<queue>

typedef pair<int,int> PII;

const int N = 1010, M = 21010;
int n,m,s;
int h[N],e[M],ne[M],w[M],idx;
int cnt;
bool st[N];
int dist[N];

void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void Dijsktra(int u){
    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push({0,u});
    dist[u]=0;
    
    while(q.size()){
        auto t=q.top();
        q.pop();
        
        int ver=t.second;
        if(st[ver]) continue;
        st[ver]=true;
        
        for(int i=h[ver];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[ver]+w[i]){
                dist[j]=dist[ver]+w[i];
                q.push({dist[j],j});
            }
        }
    }
}

int main(){
    while(cin>>n>>m>>s){
        memset(h,-1,sizeof(h));
        memset(st,0,sizeof(st));
        idx=0;
        memset(dist,0x3f,sizeof(dist));
        
        while(m--){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
        
        //建立所有车站与虚拟源点的边权为0的边
        cin>>cnt;
        while(cnt--) {
            int num;
            scanf("%d",&num);
            add(0,num,0);
        }
        
        Dijsktra(0);
        
        if(dist[s]>=0x3f3f3f3f) puts("-1");
        else printf("%d\n",dist[s]);
    }
    
    return 0;
}

2、建立反向边 P1629 邮寄员送信

https://www.luogu.com.cn/problem/P1629

题意要求我们求出邮递员从起点出发，向每个节点送一封信之后又回到起点所走的最短总距离。

从起点走向每个终点好办，可以直接一遍Dijsktra算法即可，主要是怎么求从2~n号点回到1号点的距离，直接对每个点进行Dijsktra算法显然会超时，这个时候我们就可以建立反向边

读入边时，建立1到这个点的正向边，再建立这个点编号+n到1+n的反向边，这样直接对1+n号点进行Dijsktra算法，就求出来了从每个点回到1号点走的路程

为什么要加n呢，因为两个点之间可能会有双向边，这样是为了不与原来的边重合，代码如下：

#include<iostream>
using namespace std;
#include<cstring>
#include<queue>

typedef pair<int,int> PII;

const int N = 2010, M = 2e5+10;
int hs[N],ht[N],e[M],ne[M],w[M],idx;
int dist1[N],dist2[N];
bool st[N];
int n,m;

void add(int h[],int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void Disjktra(int start,int h[],int dist[]){
    priority_queue<PII,vector<PII>,greater<PII>>q;
    memset(dist,0x3f,sizeof(dist1));
    dist[start]=0;
    q.push({0,start});
    
    while(q.size()){
        auto t=q.top();
        q.pop();
        int dis=t.first,u=t.second;
        
        if(st[u]) continue;
        st[u]=true;
        
        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];
                q.push({dist[j],j});
            }
        }
    }
}

int main(){
    cin>>n>>m;
    
    memset(hs,-1,sizeof(hs));
    memset(ht,-1,sizeof(ht));
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
//建立反向边
        add(hs,a,b,c);
        add(ht,b+n,a+n,c);
    }


//两边Dijsktra算法
    Disjktra(1,hs,dist1);
    Disjktra(n+1,ht,dist2);
    
    int res=0;
    
    for(int i=1;i<=n;i++) res+=dist1[i]+dist2[i+n];
    
    cout<<res<<endl;
    
    return 0;
}

拓展例题：https://www.luogu.com.cn/problem/CF219D 也应用到了建立反向边的思想，但是这里是用dfs求解

3、建立分层图：JLOI2011 飞行路线 - 洛谷

https://www.luogu.com.cn/problem/P4568

有k条边边权可以为0的图论问题

我们可以建立分层图，将图的点数扩大k倍，让每两层的点之间可以互相链接，这样来求得最后答案，代码如下：

#include<iostream>
using namespace std;
#include<cstring>
#include<queue>

typedef pair<int,int> PII;

const int N = 120010, M = 3e6+10;
int n,m,k,sx,sy;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c=0){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void Dijsktra(){
    memset(dist,0x3f,sizeof(dist));
    dist[sx]=0;
    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push({0,sx});
    while(q.size()){
        auto t=q.top();
        q.pop();
        
        int u=t.second,dis=t.first;
        if(st[u]) continue;
        st[u]=true;
        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];
                q.push({dist[j],j});
            }
        }
    }
}

int main(){
    cin>>n>>m>>k>>sx>>sy;
    
    memset(h,-1,sizeof(h));
    
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
//建立分层图
        for(int j=1;j<=k;j++){
            add(a+(j-1)*n,b+j*n);
            add(b+(j-1)*n,a+j*n);
            add(a+j*n,b+j*n,c);
            add(b+j*n,a+j*n,c);
        }
    }
//建立分层图
    for(int j=1;j<=k;j++)
        add(sy+(j-1)*n,sy+j*n);
    
    Dijsktra();
    
    cout<<dist[sy+n*k]<<endl;
    
    return 0;
}

这三种类型都是很经典的例题，还有一类很经典的问题也值得关注，就是最短路计数：

4、最短路计数 P1144

https://www.luogu.com.cn/problem/P1144

本题考其他所有点到1号点的最短路条数，这里只需要在求解最短路径时更新距离的时候维护一个计数数组即可，代码如下：

#include<iostream>
using namespace std;
#include<cstring>
#include<queue>

//这里用到了bfs算法求解最短路，因为边权为1，所以每次第一个遍历到的点
//一定就是最短路

const int N = 1e6+10, M = 2e6+10,mod=100003;
int h[N],e[M],ne[M],idx;
int dist[N],cnt[N];
int n,m;

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs(){
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    queue<int>q;
    q.push(1);
    cnt[1]=1;
    while(q.size()){
        int t=q.front();
        q.pop();

        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+1){
                dist[j]=dist[t]+1;
                //更新最短路数量
                cnt[j]=cnt[t];
                q.push(j);
            }
            //累加最短路数量
            else if(dist[j]==dist[t]+1) cnt[j]=(cnt[j]+cnt[t])%mod;
        }
    }
}

int main(){
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }

    bfs();

    for(int i=1;i<=n;i++) printf("%d\n",cnt[i]);

    return 0;
}

还有本人做过的一些经典好题分享给大家：

通往奥格瑞玛的道路 - https://www.luogu.com.cn/problem/P1462 求解最短路+二分

佳佳的魔法药水 - https://www.luogu.com.cn/problem/P1875 方案统计问题+最短路计数问题的综合

NOIP2009 提高组最优贸易 - https://www.luogu.com.cn/problem/P1073 这道题灵活考察了Dijsktra算法与SPFA算法的本质区别，因为距离更新时后面会有更小点更新，所以不能用Dijsktra算法，必须用SPFA算法，同时考察了灵活建图求解距离方式

USACO08OPEN Clear And Present Danger S - https://www.luogu.com.cn/problem/P2910 比较简单，主要是建图

灾后重建 - https://www.luogu.com.cn/problem/P1119 考察了Floyd算法的本质，每次用中间点进行任意两个节点之间距离的更新

奇怪的电梯 - https://www.luogu.com.cn/problem/P1135 将电梯之间层数的转移转化为图上的边的建立，之后求解最短路

跳楼机 - https://www.luogu.com.cn/problem/P3403 上一题的拓展，这里将mod x的每一种情况建立出来，求出到达mod x = i 最少需要走的y和z的次数与层数，最后进行计算累加

理解算法本质，注重灵活建图与灵活求解，把问题建立在图论上的问题求解，希望各位有所进步！！！

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S10

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S10

#最短路

登录后参与评论

0 条评论

热度