#创作计划# 最短路算法

Yichen_Xu

2026-01-21 18:44:04

发布于：北京

17阅读

0回复

0点赞

最短路算法讲解

最短路算法的概念

顾名思义，就是求两个点间的最短（边权和或边数最小）路径的算法，注意此处的路径不能有重复走过的边。

最短路算法中的常见算法

Floyd 算法

原理：通过类动态规划的方法，定义状态 f[i][j]为从 $i$ 点到 $j$ 点的最短路，我们可以枚举中间点 $k$ 表示以 $k$ 为中间点的最短路，不难看出状态转移方程为 f[i][j] = min(f[i][j],f[i][k]+f[k][j]) ，注意初始将所有两点间距离设为 $\infty$ ， $\infty$ 的实值自行确定，只要比所有边边权最大值大即可，个人建议设为 0x3f3f3f3f，存边时将对应边的距离设为对应边权。

时间复杂度：

$\operatorname{O}(n^3)$ （若无特殊说明，下文中 $n$ 默认表示节点数， $m$ 默认表示边数，图默认是连通图）

空间复杂度：

$\operatorname{O}(n^2)$

优势：

1.是全源最短路，能求任意点间最短路径长度
2.代码简单
3.适用于绝大多数图

劣势：

1.时间复杂度、空间复杂度太大

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3;//最大节点数 
int n,m;//n指节点数,m指边数
int f[N][N]; //f[i][j]指从i到j的最短路
void floyd(){
	for(int k = 1;k <= n;k ++){ //k指中间点 
		for(int i = 1;i <= n;i ++){ //起始点 
			for(int j = 1;j <= n;j ++){ //到达点 
				f[i][j] = min(f[i][j],f[i][k] + f[k][j]); //状态转移 f[i][j] = min(f[i][j],f[i][k]+f[k][j]) 
			}
		}
	}
} 
int main(){
	memset(f,0x3f,sizeof f); //f数组初始化为正无穷 (0x3f3f3f3f)，由于 memset 按字节填充，int类型4字节，所以只需要写0x3f即可
	cin >> n >> m;
	for(int i = 1;i <= m;i ++){
		int u,v,w;//每条边的起始点、到达点和边权
		cin >> u >> v >> w;
		f[u][v] = w; 
	} 
	int sx,ex;//从 sx 到 ex 的最短路 
	cin >> sx >> ex;
	floyd();
	cout << f[sx][ex];//输出 
	return 0;
}

Dijkstra 算法

原理：

我们先了解松弛操作：松弛操作就是看从源点到该点的最短路加该点到终点的边的边权有没有比源点到该点当前记录的最短路短，如果短就更新，例如目前从源点 $1$ 到点 $5$ 的距离为 $10$ ，点 $5$ 到点 $6$ 的边的距离为 $3$ ，而当前记录的最短路距离为 $15$ ，则将 $15$ 更新为 $13$ 。
Dijkstra 的算法过程为：
1.将点集划分为 $S$ 和 $T$ 两个子集， $S$ 里的节点为当前已有最短路的点， $T$ 则是还没有最短路的点，同时定义 dis[u] 为源点到点 $u$ 的距离
2.将源点加入 $S$ 集合，将源点的 dis 设为 $0$ ，并找出和该点相连的所有邻接边中边权最小的边接的点，做松弛操作
3.重复上述过程，直到松弛不了
4.输出答案
这种贪心策略每次都选最小值，也会遍历和尝试松弛每个点，正确性显然，笔者不做证明。
由于上述操作中找最小值可以使用堆（优先队列，priority_queue）优化，下面的代码和时间复杂度分析对象都为堆优化 Dijkstra 算法。

时间复杂度：

$\operatorname{O}(m \log m)$

空间复杂度：

$\operatorname{O}(n)$

优势：

1.时间复杂度较低
2.容易理解

劣势：

1.只能用于非负权图

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10; //最多节点/边数 
int n,m; //节点数和边数 
vector<pair<int,int>> g[N];//邻接表存图 
int dis[N];//到源点距离 
bool vis[N];
void dij(int sx){
	memset(dis,0x3f,sizeof dis);//设为 INF 
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;//优先队列维护最小 
	q.push({0,sx});//源点加入队列 
	dis[sx] = 0;//标记为 0 
	while(q.size()){ //直到无法松弛 
		int u = q.top().second;//去除节点 
		q.pop();
		if(vis[u]) continue;//如果已访问就下一个 
		vis[u] = 1;
		for(auto ed : g[u]){ //遍历邻接边 
			int v = ed.first;
			int w = ed.second;
			if(dis[v] > dis[u] + w){//判断松弛条件 
				dis[v] = dis[u] + w;//松弛 
				q.push({dis[v],v});//加入队列 
			}
		}
	}
}
int main(){
	cin >> n >> m; //输入 
	for(int i = 1;i <= m;i ++){
		int u,v,w;
		cin >> u >> v >> w;
		g[u].push_back({v,w});//双向存边 
		g[v].push_back({u,w});
	}
	dij(1);//默认把点1当成源点 
	cout << dis[n];//点n当做终点 
}