最短路

参考资料

• 最短路 - OI Wiki
• 最短路问题 - 维基百科

算法对比

• $n$ 代表图的点数，$m$ 代表图的边数。

算法名称	时间复杂度	最短路类型	负权图
Floyd	$O(n^3)$	全源最短路	能
Dijkstra	$O(nm)$	单源最短路	不能
Bellman–Ford	$O(m\log m)$	单源最短路	能
Johnson	$O(nm\log m)$	全源最短路	能

Floyd 算法

void floyd(int n)
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
			}
		}
	}
}

Dijkstra 算法

void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	priority_queue<pair<int,int>> q;
	q.push({0,s});
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop(); 
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,w]:G[u])
		{
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
}

例题

洛谷 B3647 【模板】Floyd

洛谷 B3647 【模板】Floyd

给定一张 $n$ 个点 $m$ 条边的无向图，求所有点对 $(i,j)$ 之间的最短路径长度。（$n\le100,m\le4500$）

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=105;
int a[N][N];
void init(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[i][j]=i==j?0:inf;
		}
	}
}
void floyd(int n)
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	init(n);
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		a[u][v]=min(a[u][v],w);
		a[v][u]=min(a[v][u],w);
	}
	floyd(n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<a[i][j]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

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

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

给定一张 $n$ 个点 $m$ 条有向边的非负权图，求从 $s$ 出发到每个点的距离。（$n\le10^5,m\le2\times10^5$）

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=100005;
vector<pair<int,int>> G[N];
int dis[N];
bool vis[N];
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	priority_queue<pair<int,int>> q;
	q.push({0,s});
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop(); 
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,w]:G[u])
		{
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,s;
	cin>>n>>m>>s;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<' ';
	}
	return 0;
}