众所周知，图论在OI中分为许多个部分。

举一些比较著名的例子：连通性问题、拓扑排序、最小生成树……

即使大家对以上问题都不太熟悉，

不过接下来我们要学习的问题，你一定耳熟能详——这就是 最短路径问题！！

---

求解最短路径的算法有许多种，但最出名的就是以下5种算法：

\(1.\operatorname{BFS}\)

当边权为 \(1\) 时，

整张图可以当作是我们以前的 \(\operatorname{BFS}\) 模型，

这时，由于已经被搜过的点 不会再进入队列，所以它的时间复杂度为 \(O(n+m)\)，属于 速度最快 的最短路算法。

只不过，

使用 \(\operatorname{BFS}\) 时，

要保证边权为 \(1\)；

否则，

\(\operatorname{WA}\) 警告！

\(2.\operatorname{Floyd}算法\)

算法介绍

此算法用来求解任意两个结点之间的最短路，我们称这种问题为 全源最短路径 。 \(Floyd算法\) 适用于任何类型的图，无论有向无向，边权正负。但是，最短路径 必须存在 。（图中不能有 负权环 ,否则最短路径为 \(-\infty\) ）

算法内容

这种算法本身其实是一种 动态规划 ，我们定义一个数组 \(dis_{x,y}\) ，其初始化值如下：

\[dis_{x,y}= \begin{cases} 0\space(x=y), \\+\infty(x\not = y) \end{cases} \]

它代表x和y之间的最短路径。于是，有状态转移方程 \(dis_{x,y}=\min(dis_{x,y},dis_{x,k}+dis_{k,y})\space(1 \le k \le n)\) ,其中 \(k\) 代表 \(x,y\) 之间的中转点。

时空复杂度

\(Floyd算法\) 的时间复杂度比较高，为 \(O(n^3)\) ，由于它的存图方式为 邻接矩阵 ，所以空间复杂度为 \(O(n^2)\) 。但是这个算法容易理解和实现，值得一学。

核心代码:

//Floyd
for(int k=1;k<=n;k++)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	}
}

\(2. Dijkstra算法\)

算法介绍

此算法用来求解 单源单汇最短路径问题 。

顾名思义，这种问题就是求 起点 (点 \(s\) ) 到终点 (点 \(e\) ) 的最短路径。

这个算法虽然好用，可是它存在一个缺点—— 不能在负权图中使用 ！

至于为什么存在这样一个缺点，下文将给出证明。

算法内容

将图中结点分成两个集合：已确定最短路长度的点集（记为 \(S\) 集合）的和未确定最短路长度的点集（记为 \(T\) 集合）。一开始所有的点都属于 \(T\) 集合。

定义一个数组 \(dis_x\) ，其初始化值为：

\[dis_{x}= \begin{cases} 0\space(x=s), \\+\infty(x\not = s) \end{cases} \]

然后重复以下操作：

1. 从 \(T\) 集合中，选取一个最短路径长度最小的结点，移到 \(S\) 集合中。

2. 对那些刚刚被加入 \(S\) 集合的结点的所有出边执行松弛操作。

直到 \(T\) 集合为空，算法结束。

PS：下面给出 松弛操作 的定义：

对于边 \((u,v)\) ， 松弛操作对应下面的式子： \(dis(v)=\min(dis(v),dis(u)+w(u,v))\) 。

这么做的含义是显然的：我们尝试用 \(S\to u\to v\) （其中 \(S\to u\) 的路径 取最短路）这条路径去更新 \(v\) 点最短路的长度，如果这条路径更优，就进行更新。

时间复杂度

有多种方法来维护操作 \(1\) 中最短路径长度最小的结点，不同的实现导致了 \(Dijkstra算法\) 时间复杂度上的差异。

暴力解决：

不使用任何数据结构进行维护，每次操作 \(2\) 执行完毕后，直接在 \(T\) 集合中 暴力 寻找最短路长度最小的结点。操作 \(2\) 总时间复杂度为 \(O(m)\) ，操作 \(1\) 总时间复杂度为 \(O(n^2)\) ，全过程的时间复杂度为 \(O(n^2+m)=O(n^2)\) 。

二叉堆：

每成功松弛一条边 \((u,v)\) ，就将 \(v\) 插入二叉堆中（如果 \(v\) 已经在二叉堆中，直接修改相应元素的权值即可），操作 \(1\) 直接取出堆顶结点即可。共计有 \(O(m)\) 次二叉堆上的 修改 操作， \(O(n)\) 次删除操作，而修改和删除的时间复杂度均为 \(O(\log n)\) ，时间复杂度为 \(O((n+m)\log n)=O(m\log n)\) 。

优先队列：

和 二叉堆 类似，但使用 优先队列 时，如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是 \(O(m)\) 的，时间复杂度为 \(O(m\log m)\) 。

斐波那契堆：

和 二叉堆 与 优先队列 类似，但 斐波那契堆 插入的时间复杂度为 \(O(1)\) ，故时间复杂度为 \(O(n\log n+m)=O(n\log n)\) ，时间复杂度最优。但因为 斐波那契堆 与 二叉堆 相比，不易实现且效率优势也不够大，不宜使用。

线段树：

和 二叉堆 原理类似，不过将每次成功松弛后插入二叉堆的操作改为在线段树上执行单点修改，而操作 \(1\) 则是线段树上的全局查询最小值。时间复杂度为 \(O(m\log n)\) 。

算法效果

在稀疏图中， \(m=O(n)\) ，使用 二叉堆 实现的 \(Dijkstra算法\) 效率优势更大；而在稠密图中， \(m=O(n^2)\) ，这时候使用 暴力做法 较 二叉堆实现 更优。

正确性证明

下面用数学归纳法证明，在 所有边权值非负 的前提下， \(Dijkstra算法\) 的正确性。

简单来说，我们要证明的，就是在执行操作 \(1\) 时，取出的结点 \(u\) 最短路均已经被确定，即满足 \(D(u)=dis(u)\) 。

初始时 \(S=\varnothing\) ，假设成立。

接下来用 反证法 证明。

设 \(u\) 点为算法中第一个在加入 \(S\) 集合时不满足 \(D(u)=dis(u)\) 的点。因为 \(s\) 点一定满足 \(D(s)=dis(s)\) ，且它一定是第一个加入 \(S\) 集合的点，因此将 \(u\) 加入 集合前， \(S\not =\varnothing\) ，如果不存在 \(s\) 到 \(u\) 的路径，则 \(D(u)=dis(u)=+\infty\) ，与假设矛盾。

于是一定存在路径 \(s\to x\to y\to u\) ，其中点 \(y\) 为 路径上第一个属于 \(T\) 集合的点，而 \(x\) 为 \(y\) 的前驱结点 \(\space\) (显然 \(x\in S\) ) 。需要注意的是，可能存在 \(s=x\) 或 \(y=u\) 的情况，即 \(s\to x\) 或 \(y\to u\) 可能是空路径。

因为在 \(u\) 结点之前加入的结点都满足 \(D(u)=dis(u)\) ，所以在 \(x\) 点加入到 \(S\) 集合时，有 \(D(x)=dis(x)\) ，此时边 \((x,y)\) 会被松弛，从而可以证明，将 \(u\) 加入到 \(S\) 时，一定有 \(D(y)=dis(y)\) 。

下面证明 \(D(u)=dis(u)\) 成立。在路径 \(s\to x\to y\to u\) 中，因为图上所有边边权非负，因此 \(D(y)\le D(x)\) 。从而 \(dis(y)\le D(y)\le D(u)\le dis(u)\) 。但是因为 \(u\) 结点在操作 \(1\) 中被取出 \(T\) 集合时， \(y\) 结点还没有被取出 \(T\) 集合，因此此时有 \(dis(u)\le dis(y)\) ，从而得到 \(dis(y)=D(y)=D(u)=dis(u)\) ，这与 \(D(u)\not =dis(u)\) 的假设矛盾，故假设不成立。

因此我们证明了，操作 \(1\) 每次取出的点，其最短路均已经被确定。命题得证。

注意到证明过程中的关键不等式 \(D(y)\le D(u)\) 是在图上所有边边权非负的情况下得出的。当图上存在负权边时，这一不等式不再成立， \(Dijkstra算法\) 的正确性将无法得到保证，算法可能会给出错误的结果。

核心代码

这里同时给出 \(O(n^2)\) 的暴力做法实现和 \(O(m\log m)\) 的优先队列做法实现。

暴力实现：

//const int N=1e5+5;
struct edge
{
	int v,w;
};
vectore[N];
int n,dis[N],vis[N];
void dijkstra(int s)
{
	memset(dis,inf,sizeof dis);
	dis[s]=0;
	for(int i=1;i<=n;i++)
	{
		int u=0,minn=inf;
		for(int j=1;j<=n;j++)
		{
			if(!vis[j]&&dis[j]dis[u]+w)
				dis[v]=dis[u]+w;
		}
	}
}

优先队列实现：

//const int N=1e5+5;
struct edge
{
	int v,w;
};
struct node
{
	int dis,u;
	bool operator>(const node &a) const
	{
		return dis>a.dis; 
	}
};
vectore[N];
int n,dis[N],vis[N];
priority_queue,greater()>q;
void dijkstra(int s)
{
	memset(dis,inf,sizeof dis);
	dis[s]=0;
	q.push((node){0,s});
	while(q.size())
	{
		int u=q.top().u;
		q.pop();
		if(vis[u])
			continue;
		vis[u]=1;
		for(auto ed:e[u])
		{
			int v=ed.v,w=ed.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push((node){dis[v],v});
			}
		}
	}
}

\(3. SPFA算法\)

算法介绍

前文提到， \(Dijkstra算法\) 不能在 负权图 中使用；于是， \(SPFA算法\) 就在最短路径算法中横空出世。

这个算法的前身是 \(Bellman\_Ford算法\) ，它可以用来解决 负权图 中的最短路径问题。

算法内容

\(SPFA算法\)本质上其实是 \(Bellman\_Ford算法\) 的 队列优化实现 ，相比于它的原型，这个算法的编程难度没有升级，而时间复杂度却会 大大降低 ，所以这里并不推荐使用 \(Bellman\_Ford算法\) 。

\(Bellman\_Ford算法\) 所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

但是，

很多时候我们并不需要那么多无用的松弛操作。

很显然，只有上一次被松弛的结点所连接的边，才有可能引起下一次的松弛操作。

那么我们用队列来维护 “哪些结点可能会引起松弛操作” ，就能只访问必要的边了。

这就是 \(SPFA算法\) 。

此算法也可以用于判断源点 \(s\) 是否能抵达一个 负权环 ，只需记录最短路经过了多少条边，当经过了至少 \(n\) 条边时，说明 \(s\) 点可以抵达一个负环。

此外，

\(SPFA算法\) 还可以用来解决 差分约束问题 。(待写)

时间复杂度

\(Bellman\_Ford算法\) 每次循环是 \(O(m)\) 的，那么最多会循环多少次呢？

在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 \(+1\) ，而最短路的边数最多为 \(n-1\) ，因此整个算法最多执行 \(n-1\) 轮松弛操作。故总时间复杂度为 \(O(nm)\) 。

但是，

如果我们使用的是 \(SPFA算法\) ，时间复杂度就可以降到 \(O(km)\space (k\le n)\) ，虽然在精心构造的测试数据下依旧会升级到 \(O(nm)\) ，但依旧是 负权图 下的不二之选。

核心代码

此处的程序含 负权环判定 。

//const int N=1e5+5;
struct edge
{
  int v,w;
};
vectore[N];
int n,dis[N],cnt[N],vis[N];
queueq;
bool SPFA(int s)
{
	memset(dis,inf,sizeof dis);
	dis[s]=0,
	vis[s]=1;
	q.push(s);
	while(q.size())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto ed:e[u])
		{
			int v=ed.v,w=ed.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)
					return 1;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return 0;
}

\(4. Johnson算法\)

算法介绍

除了时间复杂度达到 \(O(n^3)\) 的 \(Floyd算法\) 之外，还有更好的 全源最短路径 解决方案吗？

跑 \(n\) 次 \(SPFA\) ？最坏 \(O(n^2m)\) 的复杂度你受得了？？

跑 \(n\) 次 \(Dijkstra\) ？ 即使开 堆优化 也是 \(O(n^2\log m)\) 的复杂度，这也不低啊！而且还要考虑 负权图 ，限制不少呀！

那么，我们就使用 \(Johnson算法\) 来解决这个问题吧！

算法内容

\(Johnson算法\) 的本质其实就是 跑 \(n\) 次 \(Dijkstra算法\) 。

这么做，就是因为在三个算法的时间复杂度中，有 \(O(n^2\log m) ，即 堆优化 的 \(Dijkstra算法\) 最优。

可是，众所周知，

\(Dijkstra算法\) 无法解决在负权图下的最短路径问题！！

不过， \(Johnson算法\) 既然成立了，它就必定有 解决方案！

我们创造一个 超级源点 \(0\) ，它到图上 所有点 的权值为 \(0\) ，从这个点开始跑 \(SPFA\) ，以及 判断负权环 。

跑完以后，我们将从 源点 \(0\) 到图上所有点的最短路径长度记为 \(h_i\space(1\le i\le n)\)

假设存在一条源点为 \(u\) ，汇点为 \(v\) ，边权为 \(w\) 的边 \((u,v,w)\) ，则其边权将被 重新标注 为 \(w+h_u-h_v\) 。

如此，跑 \(n\) 遍 \(Dijkstra算法\) 以后，程序结束。

PS：算出答案后，要将答案 减去 \((h_u-h_v)\)
。

正确性证明

为什么 这种标注方式 是正确的呢？

首先，一条边 \((u,v,w)\) 的边权 \(w\) ，满足三角形不等式 \(h_u+w\ge h_v\) ，

根据 不等式性质 ，

可以将其变形为 \(w+h_u-h_v\ge 0\) ，于是， \(w\) 只需加上 \((h_u-h_v)\) 即可满足 非负性 。

请记住，答案要 减去 \((h_u-h_v)\) ！！

核心代码

虽然 \(Johnson算法\) 很不错，但是它在一般的OI竞赛中很少用到，

故不粘贴代码。

---

总结：

\(Dijkstra\) 和 \(SPFA\) 是现在 主流 的两大算法，

如果有负权边，就用 \(SPFA\) 。

没有，就用 \(Dijkstra\) 。