Dijkstra与Floyd求最短路算法简介

前言

求最短路问题很常见，有的是让求一个图中两个点的最短距离或者是求某一点到另外一点的最小代价，总之学会求最短路是很重要的

1.Dijkstra（用于计算单源、正权边的最短路问题）

大致讲解

Dijkstra 算法是一种用于求解带非负权值边的图中，单源最短路径的经典贪心算法。它的核心思想是：从起点出发，每次轮选择当前距离起点最近的未确定节点，以此为中间点更新其他节点的距离，直到所有节点的最短路径都被确定。

其实Dijkstra算法就是利用贪心算法来进行操作的，不断找与自己相连接的点，并遍历这些点中与自己相邻最近的点，一直遍历到最后。
过程：
1.每次从未标记的节点中选择距离出发点最近的节点，标记，收录到最优路径集合中

2.计算刚加入节点A的邻近节点B的距离（不包含标记的节点），若（节点A的距离+节点A到B的边长）<节点B的距离，就跟新节点B的距离与前面点
例子：
给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。

输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=2e5+5;
vector<pii>ve[N];  // 邻接表：ve[u]存储u的所有出边，每个元素是(v, w)表示u→v的边权为w
bool vis[N]; // 标记节点是否已确定最短路径
int d[N]; // 存储起点到各节点的最短距离
const int INF =1e18;
signed main()
{
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		ve[u].push_back({v,w});//由于是有向边，所以单向建
		//ve[v].push_back({u,w});如果要双向建，就加上这个
	}
	// 优先队列（小根堆）：为了快速获取距离最小的节点
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	pq.push({0,s});
	for(int i=1;i<=n;i++)
		{
			d[i]=INF;//先把距离赋值为不可达，就是非常大，为了后面比较大小
		}
		d[s]=0;//起始点到自己距离为0
	while(!pq.empty())
	{
		pii x=pq.top(); // 取距离最小的节点
		pq.pop();
		if(vis[x.se])//如果已经被标记过就直接跳过，说明已经遍历过这个点
		{
			continue;
		}
		vis[x.se]=1;//标记为遍历过
		for(auto it:ve[x.se])//遍历其子节点
		{
			if(!vis[it.fi]&&it.se+x.fi<d[it.fi])//得到最小距离
			{
				d[it.fi]=it.se+x.fi;// 更新v的最短距离
				pq.push({d[it.fi],it.fi});
			}
   //         下面这个看起来更直观
   //         int v = it.fi, w = it.se;
   //         if(!vis[v] && d[v] > d[u] + w)
   //         {
   //         d[v] = d[u] + w;
   //         pq.push({d[v], v});
   //         }
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i])//可达
	    cout<<d[i]<<" ";
	    else//不可达
	    cout<<"2147483647"<<" ";
	}
	return 0;
} 

例题：

1.P3371 【模板】单源最短路径（弱化版）

P3371 【模板】单源最短路径（弱化版）
上面的讲解代码就是这个题的AC代码

2.P4779 【模板】单源最短路径（标准版）

P4779 【模板】单源最短路径（标准版）
这题与上面题类似，代码稍微修改一下就行了，不再过多叙述

3.P1339 [USACO09OCT] Heat Wave G

P1339 [USACO09OCT] Heat Wave G

依旧类似于模板

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=1e4;
const int INF=0x3f3f3f3f;
int a[N];
bool vis[N];
vector<pii>ve[N];
signed main()
{
	IOS;
	int n,m,s,t;
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		ve[u].push_back({v,w});
		ve[v].push_back({u,w});
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=INF;
	}
	a[s]=0;
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	pq.push({0,s});//入的是要求的点
	while(!pq.empty())
	{
		pii x=pq.top();
		pq.pop();
		if(vis[x.se])
		{
			continue;
		}
		vis[x.se]=1;
		for(auto it:ve[x.se])
		{
			if(!vis[it.fi]&&it.se+x.fi<a[it.fi])
			{
				a[it.fi]=it.se+x.fi;
				pq.push({a[it.fi],it.fi});
			}
		}
	}
	cout<<a[t];
	return 0;
 } 

4.P2984 [USACO10FEB] Chocolate Giving S

P2984 [USACO10FEB] Chocolate Giving S

这题第一眼可能觉得就是求两段最短路径，求两次就行了，但是这样会超时，从题目中可以发现无论怎么走都要经1点，所以直接求从1到另外两点的最短距离就行了。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=2e5+6;
const int INF=0x3f3f3f3f;
int a[N];
bool vis[N];
vector<pii>ve[N];
signed main()
{
	IOS;
	int n,m,b;
	cin>>n>>m>>b;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		ve[u].push_back({v,w});
		ve[v].push_back({u,w});
	}
	memset(a,INF,sizeof(a));
	memset(vis,0,sizeof(vis));
	a[1]=0;
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	pq.push({0,1});
	while(!pq.empty())
	{
		pii x=pq.top();
		pq.pop();
		if(vis[x.se])
		{
			continue;
		}
		vis[x.se]=1;
		for(auto it:ve[x.se])
		{
			if(!vis[it.fi]&&it.se+x.fi<a[it.fi])
			{
				a[it.fi]=it.se+x.fi;
				pq.push({a[it.fi],it.fi});
			}
	    }
	}
	while(b--)
	{
		int s,t;
		cin>>s>>t;
		cout<<a[s]+a[t]<<endl;//最后相加就行了
	}
	return 0;
 } 

5.小美想游泳

小美想游泳

这个题实际上就是就最小瓶颈路径，即路径中边权最大值最小的路径
我们依旧可以用Dijkstra写，再定义一个数组代表从起始点到该点的路上的最大距离，在不断向最近的点延伸时，比较出最大值，遍历完后输出就行了

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=2e5+6;
int d[N];
bool vis[N];
vector<pii>ve[N];
const int INF=1e18;
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,a;
		cin>>u>>v>>a;
		ve[u].push_back({v,a});
        ve[v].push_back({u,a});
	}
	int s,t;
	cin>>s>>t;
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int i=1;i<=n;i++)
	{
		d[i]=INF;
	}
	pq.push({0,s});
	d[s]=0;
	while(!pq.empty())
	{
		pii x=pq.top();
		pq.pop();
		if(vis[t])
		{
			cout<<d[t];//到了就直接退出
			break;
		}
		if(vis[x.se])
		{
			continue;
		}
		vis[x.se]=1;
		for(auto it:ve[x.se])
		{
			if(!vis[it.fi]&&d[it.fi]>max(it.se,x.fi))
			{
				d[it.fi]=max(it.se,x.fi);
				pq.push({d[it.fi],it.fi});
			}	
		}
	}
	return 0;
}

上面都是一些相对简单的题，都可以写

2.Floyd（Floyd-Warshall 是多源最短路径算法，支持正边权和负边权（无负权回路时））

大致讲解

Floyd 算法是一种动态规划思想的全源最短路径算法，能一次性求出图中所有顶点之间的最短路径长度，支持有向图和无向图（无向图可视为双向有向图），但不允许存在负权回路（会导致路径长度无限减小）。

就是通过逐步引入中间节点，更新任意两个节点之间的最短路径。

1. 初始状态
   我们用一个n×n的矩阵dp表示节点间的距离，其中dp[i][j]表示从节点i到节点j的初始距离：

   • 若i == j（自身到自身），距离为0；
   • 若i和j直接相连，距离为边的权重；
   • 若i和j不直接相连，距离为一个极大值（表示不可达）。

2. 逐步引入中间节点优化路径
   算法的关键是通过三重循环，依次将每个节点k作为中间节点，尝试优化所有节点对(i, j)的路径：

   • 对于每个中间节点k，检查是否存在一条路径i → k → j，其总距离比当前已知的i → j的距离更短；
   • 如果更短，则更新dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])。

   形象地说：“如果从i到k再到j比直接从i到j更近，就走这条新路径”。

3. 最终结果
   当所有节点都被作为中间节点尝试过之后，dp[i][j]就存储了从i到j的最短路径距离。

例题：给出一张由 n 个点 m 条边组成的无向图。
​求出所有点对 (i,j) 之间的最短路径。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
int dp[106][106];//表示顶点i到顶点j的最短路径长度
signed main()
{
	int n,m;
	cin>>n>>m;
	memset(dp,0x3f3f3f3f3f,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		dp[i][i]=0;
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		dp[u][v]=min(dp[u][v],w);
		dp[v][u]=min(dp[v][u],w);
	}
	for(int k=1;k<=n;k++)// 枚举中间顶点k
	{
		for(int i=1;i<=n;i++)//枚举起点i
		{
			for(int j=1;j<=n;j++)//枚举终点j
			{
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);//比较路径是否更短
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

例题

1.B3647 【模板】Floyd

B3647 【模板】Floyd
就是一个简单的模板题

2.[USACO07NOV] Cow Hurdles S

[USACO07NOV] Cow Hurdles S

这题其实就类似于上面的小美想游泳，也是一个求最小瓶颈路径，即路径中边权最大值最小的路径
只不过用Dijkstra过不了，会时间超限，所以可以用Floyd

• 状态定义：dp[i][j] 表示从节点i到节点j的最小瓶颈（即i→j所有路径中，边权最大值的最小值）。
• 状态转移：对于中间节点k，i→j的路径可拆分为i→k→j。该拆分路径的瓶颈是 max(dp[i][k], dp[k][j])（i→k的最小瓶颈与k→j的最小瓶颈的最大值）。若此值比当前dp[i][j]更小，则更新dp[i][j]。
• 初始状态
  • 若i == j（自身到自身）：dp[i][j] = 0（无路径，瓶颈为 0）。
  • 若i与j直接相连（边权为w）：dp[i][j] = w。
  • 若i与j不直接相连：dp[i][j] = INF（初始化为无穷大，代表不可达）

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N=1e3+6; // Floyd算法适合n较小的场景（n≤1e3）
int dp[N][N];
signed main()
{
	int n,m,q;
	cin>>n>>m>>q;
	memset(dp,INF,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
	    dp[i][i]=0;
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		dp[u][v]=min(dp[u][v],w);//初始化直接相连的节点的瓶颈
		// 若为无向图，需加 dp[v][u] = min(dp[v][u], w);
	}
	//Floyd核心：通过中间节点k松弛所有i→j的路径
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)// 若i→k和k→j均可达，且拆分路径的瓶颈更小，则更新
			{
				if(dp[i][k]!=INF&&dp[k][j]!=INF) 
				dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j]));
			}
		}
	}
	while(q--)
	{
		int s,t;
		cin>>s>>t;
		if(dp[s][t]!=INF)
		cout<<dp[s][t]<<endl;//可达
		else cout<<"-1"<<endl;//不可达
	}
	return 0;
}

总结

以上仅是本人对Dijkstra与Floyd的理解，如果有错误，烦请指出