最短路学习笔记

xiaoniu142857

1024人浏览 · 2025-12-06 21:54:45

xiaoniu142857 · 2025-12-06 21:54:45 发布

0x01 前置芝士

路径

路径可以使有限或无限的。一条有限路径是一个边的序列 ${e_n\}$ ，使得存在一个顶点序列 ${v_{n+1}\}$ 满足 $e_i=(v_{i},v_{i+1})$ ，其中 $i\in [1,n]$ 。

$v_1$ 称为路径的起点， $v_{n+1}$ 称为路径的终点。

对于无权图，路径的长度通常定义为它所经过的边的数量。
对于有权图，路径的长度定义为它所经过的边权之和。

最短路

即为从某个点 $s$ 到某个点 $t$ 的所有路径中最短的一条。

最短路具有一个性质：无负环图上两点间的最短路一定是简单路径。

直观理解：如果不是简单路径，那么路径上一定有环。因为没有负环，所以这个环的长度一定非负。因此不走这个环一定不会更劣。

因此，最短路一定不会重复经过某个边或点。因此在一张 $n$ 个点的图上，最短路最多包含 $n$ 个点， $n - 1$ 条边。

如果 $s\to t$ 没有路径，一般认为最短路长度为 $+\infty$ 。

单源最短路：求从一个固定起点 $s$ 到图上其他所有点的最短路。
全源最短路：求图上任意有序点对 $(s, t)$ 间的最短路。

0x02 算法比较

其中 $n$ 为点数， $m$ 为边数。

算法	适用于	求解类型	时间复杂度
Floyd	任意图	全源	$O(n^3)$
Dijkstra	非负权图	单源	$\log m)$
Bellman-Ford	任意图	单源	$O (nm)$
SPFA	任意图	单源	$O (nm)$
Johnson	任意图	全源	$O(n^2 \log (n+m))$

0x03 约定记号

$s$ ：路径起点。
$t$ ：路径终点。
$w_{u,v}$ ：图上有向边 $(u, v)$ 的边权。对于每条无向边 $(u, v)$ 我们一般拆成两条有向边 $(u, v)$ 和 $(v, u)$ 。
$dis_u$ ：算法执行到当前步骤时 $s\to u$ 的最短路长度。
$D_u$ ： $s\to u$ 的实际最短路长度。

0x04 Floyd

算法过程

采用由小子图逐渐扩展到全图的 DP 思想，在扩展过程中更新最短路长度。

设 $f_{k,i,j}$ 表示经过由节点 $1\sim k$ 构成的子图， $i\to j$ 的最短路长度。

初始化时，如果存在边 $(i, j)$ 则 $f_{0,i,j}=w(i,j)$ ，否则 $f_{0,i,j}=+\infty$ ，而 $f_{i,i}=0$ 。状态转移方程为 $f_{k,i,j}=\min(f_{k-1,i,j},f_{k-1,i,k}+f_{k-1,k,j})$ 。最终 $f_{n,i,j}$ 即为 $\to j$ 最短路长度。

发现 $f_k$ 只依赖于 $f_{k-1}$ ，所以可以用滚动数组压掉 $k$ 这一维。

这个算法时间复杂度为 $O(n^3)$ ，通常使用邻接矩阵存图，邻接矩阵直接当作初始 DP 数组（ $n$ 不会太大，一般不超过 $500$ ）。

要判断是否有负环，只需要在最后一步判断 f[u][u] 的值是否有 $< 0$ 的。如果有，则 $u$ 一定在一个负环上。但是 Floyd 只能判断某点是否在负环上，而不能判断某点是否能到达一个负环。

例如由点 $1, 2$ 构成的图，其中边 $(1, 2)$ 权值为 $1$ ，自环 $(2, 2)$ 权值为 $- 1$ 。显然点 $2$ 在负环上，点 $1$ 不在负环上但可达负环。运行 Floyd 算法后会发现 $f_{2,2}=-2$ ，但是 $f_{1,1}=0$ ，因为从点 $1$ 进入负环后就出不来了。

模板代码（洛谷 B3647）

#include <bits/stdc++.h>
using namespace std;
constexpr int N=105;
int f[N][N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m,u,v,w;
    memset(f,0x3f,sizeof(f));
    cin>>n>>m;
    while(m--){
        cin>>u>>v>>w;
        f[u][v]=min(f[u][v],w);
        f[v][u]=min(f[v][u],w);
    }
    for(int i=1;i<=n;++i) f[i][i]=min(f[i][i],0);
    for(int k=1;k<=n;++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]);
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cout<<f[i][j]<<' ';
        }
        cout<<'\n';
    }
}

0x05 Dijkstra

算法过程

Dijkstra = BFS + 贪心。该算法将结点分成两个集合：已确定最短路长度的点集 $S$ 的和未确定最短路长度的点集 $T$ 。初始所有的点都在 $T$ 中。

我们先定义一下松弛操作：对于有向边 $(u, v)$ 执行松弛操作，即为令 $dis_v=\min(dis_v,dis_u+w_{u,v})$ 。即我们尝试使用路径 $s\to u\to v$ 的长度更新 $dis_v$ 。记好这个操作，因为后面的 Bellman-Ford 和 SPFA 算法都要用到它！

Dijkstra 算法包含以下步骤：

初始化 $dis_s=0$ ，其他点的 $d i s$ 均为 $+\infty$ 。
从 $T$ 集合中取出 $d i s$ 最小的点，加入 $S$ 。
对刚刚加入 $S$ 集合的点的所有出边执行松弛操作。
不断重复步骤 2 和 3，直到 $T=\varnothing$ 。

在实现时使用 STL 内置的 priority_queue 优先队列实现集合 $T$ 。该容器是一个大根堆，出入队时间复杂度均为一只 $\log$ 。

Dijkstra 算法中，pop 操作执行 $n$ 次，而 push 操作最多执行 $m$ 次。因此队列中最多 $m$ 个节点，时间复杂度为 $\log m)$ 。

正确性证明

我们要证明在边权非负时 Dijkstra 算法是正确的。即我们要证明每次执行步骤 2 被取出的点 $u$ 此时一定满足 $dis_u=D_u$ 。下面采用反证法证明。

对于 $s$ ， $D_s=0$ ，被取出时 $dis_s=0$ ，此时是正确的。

假设 $u$ 为第一个在被取出时 $dis_u>D_u$ 的节点。显然 $u\neq s$ ，因此此时 $S$ 一定非空，因为其中有 $s$ 。

设 $\to u$ 的最短路形如 $\to x \to y \to u$ ，其中 $x$ 是路径上最后一个在 $u$ 被取出时属于 $S$ 的节点， $x$ 可以等于 $s$ ，而 $y$ 是 $x$ 的后继， $y\neq u$ 且它还在 $T$ 中。

下面我们来证明一定会存在一个这样的 $y$ 点。如果不存在，则 $u$ 的前驱 $v$ 在加入 $S$ 时一定有 $dis_v=D_v$ 。此时 $v$ 对它的出边 $(v, u)$ 进行松弛时 $dis_u$ 会被更新成正确的最短路 $D_u$ 。这与原假设矛盾。

而在 $x$ 被取出 $T$ 并加入 $S$ 时 $dis_y$ 会被边 $(x, y)$ 更新成 $D_y$ ，获得正确的最短路。因此 $y$ 被取出时一定有 $D_y=dis_y$ 。由于边权非负，有 $D_y\le D_u\le dis_u$ 。由于 $u$ 被取出了 $T$ 而 $y$ 仍然在 $T$ 中，因此 $D_y=dis_y\ge dis_u$ 。故 $D_y=D_u=dis_u$ ，与原假设矛盾。因此算法正确。

模板代码（洛谷 P4779）

#include <bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5;
struct Node{
	int u,dis;
	inline bool operator<(const Node &rhs) const {
		return dis>rhs.dis;  // priority_queue是大根堆，因此这里要反过来 
	}
};
vector<pair<int,int>> g[N];
int dis[N];
void dijkstra(int s){
	priority_queue<Node> q;
	memset(dis,0x3f,sizeof(dis));
	q.push({s,dis[s]=0});
	while(!q.empty()){
		Node t=q.top();q.pop();
		if(dis[t.u]<t.dis) continue;
		for(auto [v,w]:g[t.u]){
			if(dis[t.u]+w<dis[v]){
				dis[v]=dis[t.u]+w;
				q.push({v,dis[v]});
			}
		}
	} 
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n,m,s,u,v,w;
	cin>>n>>m>>s;
	while(m--){
		cin>>u>>v>>w;
		g[u].emplace_back(v,w);
	}
	dijkstra(s);
	for(int i=1;i<=n;++i) cout<<dis[i]<<' ';
	return 0;
}

0x06 Bellman-Ford

算法过程

Bellman-Ford 算法中，初始 $dis_s=0$ ，其它点的 $dis=+\infty$ 。每轮中我们对每条边进行松弛操作，一共进行 $n - 1$ 轮。因此时间复杂度为 $O (nm)$ 。

如果从 $s$ 出发能到达一个负环，那么在负环上的松弛操作会永远持续。因此如果 $n - 1$ 轮松弛执行完毕仍存在可以松弛的边，则存在负环。

正确性证明

图上任意两点间最短路最多有 $n - 1$ 条边（除非存在负环）。而每一轮松弛都会将每个点的最短路推进一条边。因此最多执行 $n - 1$ 轮即可得到正确答案。

注：该算法由于时间复杂度过大，一般在 OI 中不会使用它，通常使用其队列优化 SPFA 替代。本人从未见过裸 Bellman-Ford 算法的题，因此这里先不提供模板代码。

0x07 SPFA

算法过程

SPFA 是对 Bellman-Ford 算法的队列优化。

我们约定，对于有向边 $(u, v)$ 执行松弛操作时，若 $dis_u+w_{u,v}<dis_v$ ，则称这次操作为有效的。

注意到，对于任何有效松弛操作， $dis_u$ 一定不能等于 $+\infty$ 。而只有上一次被有效松弛的点的出边才可能引起下一次有效松弛。因此用队列维护这些刚刚被有效松弛的点。

若要判负环，则记录起点到每个点最短路经过的边数。若边数 $\geq n$ ，则有负环。

这样时间复杂度上限仍为 $O (nm)$ ，但通常可以得到很大的优化，比 Bellman-Ford 算法快很多。

模板代码（洛谷 P3385）

#include <bits/stdc++.h>
using namespace std;
constexpr int N=2005,INF=0x3f3f3f3f;
vector<pair<int,int>> g[N];
int dis[N],cnt[N],n;
bool inq[N];  // 标记每个点是否在队列中 
bool spfa(){
	queue<int> q;
	q.push(1);
	dis[1]=0;
	inq[1]=true;
	while(!q.empty()){
		int u=q.front();q.pop();
		inq[u]=false;
		for(auto [v,w]:g[u]){
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n) return true;
				if(!inq[v]){
					q.push(v);
					inq[v]=true;
				}
			}
		}
	}
	return false;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int T,m,u,v,w;
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;++i){
			g[i].clear();
			dis[i]=INF;
			cnt[i]=0;
			inq[i]=false;
		}
		while(m--){
			cin>>u>>v>>w;
			if(w<0) g[u].emplace_back(v,w);
			else{
				g[u].emplace_back(v,w);
				g[v].emplace_back(u,w);
			}
		} 
		if(spfa()) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

0x08 Johnson

Johnson 和 Floyd 一样，是一种能求出无负环图上任意两点间最短路径的算法。

算法过程

注意到，如果这个图是非负权图，那么我们可以直接枚举起点，跑 $n$ 次 Dijkstra。

对任意图的的边权预处理，使得每条边的新边权非负，同时又能通过新图上的最短路求出原图中的最短路。

我们新建一个虚点 $0$ ，从这个点向每个点连长度为 $0$ 的边。接下来我们使用 SPFA 求出 $0$ 号点到每个点 $i$ 的最短路 $h_i$ 。假如存在一条从 $u$ 到 $v$ 的边，将它的边权重新设为 $h_u-h_v+w_{u,v}$ 。可以证明，这个边权一定是非负的。

接下来以每个点为起点各跑一遍 Dijkstra 即可。若采用优先队列优化，则时间复杂度为 $O(n^2 \log (n+m))$ 。

正确性证明

在新图上，对于一条路径 $s\to v_1 \to v_2 \to \dots \to v_n \to t$ ，它的长度表达式如下：
$(h_s-h_{v_1}+w_{s,v_1})+(h_{v_1}-h_{v_2}+w_{v_1,v_2})+ \dots +(h_{v_n}-h_t+w_{v_n,t})$
化简得：
$w_{s,v_1}+\dots+w_{v_n,t}+h_s-h_t$
无论从 $s$ 到 $t$ 走什么路径， $h_s-h_t$ 永远为常数。因此新图上的最短路就是原图上的最短路。

接下来证明重新标注的图的边权非负。对于有向边 $(u, v)$ ，显然有 $h_u+w_{u,v} \ge h_v$ ，因此 $h_u-h_v+w_{u,v}\ge 0$ ，证毕。

模板代码（洛谷 P5905）

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3005,M=9005,INF=0x3f3f3f3f3f3f3f3f,C=1e9;
struct Edge{int to,w,nxt;} e[M];
struct Node{
    int u,dis;
    inline bool operator<(const Node &rhs) const{
        return dis>rhs.dis;
    }
};
int hd[N],cnt[N],h[N],dis[N],tot,n;
bool inq[N];
inline void add(int u,int v,int w){
    e[++tot]={v,w,hd[u]},hd[u]=tot;
}
bool spfa(){
    queue<int> q;
    memset(h,0x3f,sizeof(h));
    q.push(0);
    inq[0]=true;
	h[0]=cnt[0]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        inq[u]=false;
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].w;
            if(h[u]+w<h[v]){
                h[v]=h[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>n) return true;
                if(!inq[v]){
                    q.push(v);
                    inq[v]=true;
                }
            }
        }
    }
    return false;
}
void dijkstra(int s){
    priority_queue<Node> q;
    memset(dis,0x3f,sizeof(dis));
    q.push({s,dis[s]=0});
    while(!q.empty()){
        Node t=q.top();q.pop();
        if(dis[t.u]<t.dis) continue;
        for(int i=hd[t.u];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].w;
            if(dis[t.u]+w<dis[v]){
            	dis[v]=dis[t.u]+w;
                q.push({v,dis[v]});
            }
        }
    }
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
    int m,u,v,w,ans;
    cin>>n>>m;
    while(m--){
    	cin>>u>>v>>w;
        add(u,v,w);
    }
    for(int i=1;i<=n;++i) add(0,i,0);
    if(spfa()){
    	cout<<"-1";
        return 0;
    }
    for(int u=1;u<=n;++u){
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].to;
            e[i].w=h[u]-h[v]+e[i].w;
        }
    }
    for(int u=1;u<=n;++u){
        ans=0;
        dijkstra(u);
        for(int v=1;v<=n;++v){
            if(dis[v]==INF) ans+=v*C;
            else ans+=v*(dis[v]-h[u]+h[v]);
        }
        cout<<ans<<'\n';
    }
    return 0;
}