最短路算法入门

最短路问题是算法竞赛中非常常见的一类问题，在这里我们只需要考虑有向图上的算法，因为无向图是特殊的有向图(对于无向图中的每条边 u ↔ v u\leftrightarrow v u↔v都可以转化为有向图中的 u → v u\rightarrow v u→v和 v → u v\rightarrow u v→u)

图的存储

图的存储一般有两种形式：

1、邻接矩阵存储，开一个二维数组 g [ N ] [ N ] g[N][N] g[N][N]，其中 g [ i ] [ j ] g[i][j] g[i][j]表示 i i i与 j j j之间的边权。

2、邻接表存储，使用数组模拟链表为每个点开出单链表，分别存储该点的所有邻边。

最短路算法

最短路算法一般分为两大类：

1、单源最短路算法，常用的有:

​ ( I I I) D i j k s t r a Dijkstra Dijkstra算法，该算法要求所有边的边权都为正值。在稠密图上的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，稀疏图上的时间复杂度为 O ( m l o n g n ) O(mlongn) O(mlongn),当然可以通过堆优化的方式降低复杂度。

​ ( I I ) (II) (II) S p f a Spfa Spfa算法，该算法对边权的正负没有要求，算法平均时间复杂度为 O ( m ) O(m) O(m)。

2、多元最短路算法，一般使用 F l o y d Floyd Floyd算法，通过三重循环进行距离的更新，时间复杂度为 O ( n 3 ) O(n^3) O(n3)。

算法模板

单源最短路算法部分以链接中题目为例热浪(题面见文章结尾)

1、 D i j k s t r a Dijkstra Dijkstra算法(朴素版本) O ( n 2 ) O(n^2) O(n2)：

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int n, m, beg, ed;
int g[N][N]; // 使用邻接矩阵的形式存储图
int dist[N]; // dist数组存储每个点到起点的最短距离
bool st[N]; // st存储每个点是否已经被更新为最短距离
inline int Dijkstra() {
    memset(dist,0x3f,sizeof dist); // 初始化距离为充分大的数防止影响更新
    dist[beg] = 0; // 起点到起点的距离为0
    for (int i = 1; i <= n; i++) {
        int t = -1; // 通过t标记现在存在的最短距离点用于更新
        for (int j = 1; j <= n; j++) {
            if (!st[j]&&(t==-1||dist[t]>dist[j])) {
                t = j; // 当前点没有更新最短距离且满足距离比标记距离更短
            }
        }
        st[t] = true;; // 更新过点后进行标记
        for (int j = 1; j <= n; j++) {
            dist[j] = fmin(dist[j],dist[t]+g[t][j]);
        }
    }
    return dist[ed];
}
int main() {
    scanf("%d%d%d%d",&n,&m,&beg,&ed);
    memset(g,0x3f,sizeof g); // 先将每两个点之间的距离初始化为一个充分大的数
    // 防止在更新最短距离的时候因为系统默认初始值0而影响结果
    for (int i = 1; i <= m; i++) {
        int a, b, c; scanf("%d%d%d",&a,&b,&c);
        g[a][b] = g[b][a] = fmin(g[a][b],c); //是无向图且可能含有重边
    }
    printf("%d",Dijkstra());
    return 0;
}

2、 D i j k s t r a Dijkstra Dijkstra算法(堆优化版本) O ( ( m + n ) l o g m ) O((m+n)logm) O((m+n)logm):

#include<bits/stdc++.h>
using namespace std;
const int N = 2510, M = 12410;
int n, m, beg, ed;
int h[N],e[M],w[M],ne[M],idx; // 使用邻接表的形式存储图
int dist[N];
bool st[N];
inline void add(int a,int b,int c) {
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
} // 在a到b之间加一条边权为c的边
inline int Dijkstra() {
	memset(dist,0x3f,sizeof dist);
	dist[beg] = 0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>heap;
	heap.push({0,beg}); // 将距离和当前距离对应的点一起存入堆中
	while(heap.size()) {
		auto t = heap.top(); heap.pop(); // 每次取出堆顶点进行更新用于更新距离
		int val = t.first, id = t.second;
		if (st[id]) continue;
		st[id] = true;
		for (int i = h[id]; ~i; i=ne[i]) {
			int j = e[i];
			if (dist[j] > val + w[i]) {
				dist[j] = val + w[i];
				heap.push({dist[j],j});
			}
		}
	}
	return dist[ed];
}
int main() {
	scanf("%d%d%d%d",&n,&m,&beg,&ed);
	memset(h,-1,sizeof h);
	for (int i = 1; i <= m; i++) {
		int a, b, c; scanf("%d%d%d",&a,&b,&c);
		add(a,b,c),add(b,a,c); // 由于是无向图所以在a,b和b,a之间都需要加边
	}
	printf("%d",Dijkstra());
	return 0;
}

3、 S p f a Spfa Spfa算法 O ( m ) O(m) O(m):

#include<bits/stdc++.h>
using namespace std;
const int N=2510,M=12410;
int n, m, beg, ed;
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
bool st[N];
inline void add(int a,int b,int c) {
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa(){
	memset(dist,0x3f,sizeof dist);
	queue<int> q; // 队列中存储已经更新好距离的点
	q.push(beg); dist[beg] = 0;
	st[beg] = true; 
	while (q.size()) {
		auto t = q.front(); q.pop();
		st[t] = false;
		for (int i = h[t]; ~i; 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);
				}
			}
		}
	}
}
int main(){
	scanf("%d %d %d %d",&n,&m,&beg,&ed);
	memset(h,-1,sizeof h);
	for (int i = 1; i <= m; i++) {
		int a, b, c; scanf("%d %d %d",&a,&b,&c);
		add(a,b,c),add(b,a,c);
	}
	spfa();
	printf("%d",dist[ed]);
	return 0;
}

多源最短路算法部分以链接中题目为例Floyd求最短路(题面见文章结尾)

4、 F l o y d Floyd Floyd算法 O ( n 3 ) O(n^3) O(n3):

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int n,m,t;
int dist[N][N]; // dist[i][j]存储点i到j的最短距离
inline int read(){ //快读部分，可以用scanf代替
	char ch=getchar(); int id=1,res=0;
	while('0'>ch||ch>'9'){if(ch=='-') id=-1; ch=getchar();}
	while('0'<=ch&&ch<='9'){res=(res<<1)+(res<<3)+(ch^48); ch=getchar();}
	return res*id;
}
int main(){
	n=read(),m=read(),t=read();
    // scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i==j) dist[i][j]=0;
			else dist[i][j]=0x3f3f3f3f; 
	for(int i=1;i<=m;i++) {
		int a=read(),b=read(),c=read();
		dist[a][b]=fmin(dist[a][b],c);
	}
    // 只要满足通过先通过中间点再到目标点的距离小于直接到目标点的距离近就去更新
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dist[i][j]=fmin(dist[i][j],dist[i][k]+dist[k][j]);
	while(t--) {
		int x=read(),y=read();
		if(dist[x][y]>0x3f3f3f3f>>1) printf("impossible\n");
		else printf("%d\n",dist[x][y]);
	}
	return 0;
}

题面(热浪)

题面(Floyd求最短路)

本文章基于AcWing算法基础课制作