最短路与 Floyd 算法

最短路

什么是最短路？

最短路，指在一张图上，两点之间一条合法可到达的路径中边权值和最小或是边数最少的路径。

名词解释

单源最短路：从一个点出发，到其他所有点的最短路长度；
全源最短路：图上点中两两点对之间的最短路；
松弛操作：在一张图上，用一个节点已经算出的最短路长度更新其他节点（通常为邻接节点）的最短路长的操作。

求解算法

求解的方式大致有以下几种：

Floyed 全源最短路算法
Bellman-Ford 单源最短路算法
SPFA 单源最短路算法
Dijkstra 单月最短路算法
Johnson 全源最短路算法

Floyd 算法

floyd 这个名字很有意思，写成 floyed 也是对的，在不同的地方可能会看到不同的写法，但是都指这一种全员最短路算法，自己也可以按照书写习惯选择写哪一种。

算法实现过程

Floyd 算法的实现过程类似 dp，其核心思想就是中介点 $k$ ，对于 $dis[i][j]$ 的计算，可以以 $k$ 作为中介点，更新 $dis[i][j]$ 的取值，易得状态转移方程为： $dp[i][j]=min\{dis[i][j],dis[i][k]+dis[k][j]\}$ ，其中 $dis[u][v]$ 表示点 $v$ 与点 $u$ 之间的最短路径长。

经过上述对于算法过程的探讨，可以大概地得到算法框架，即分别对 $i$ ， $j$ 和 $k$ 进行三层循环，在循环时利用状态转移方程进行松弛操作，时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。

注意：一开始时，如果 $u$ 和 $v$ 之间有边，那么 $dis[u][v]$ 就为这条边的权值，否则 $dis[u][v]$ 就应当初始化为 $inf$ 。

循环顺序

在解决区间 dp 问题时，我们的循环顺序是代码正确与否的关键之处，对于 Floyd 算法， $i$ ， $j$ 和 $k$ 三层循环的里外顺序极其讲究，如果第一二两层分别循环 $i$ 和 $j$ ，那么可能出现在利用 $k$ 作为中介点更新的时候， $dis[i][k]$ 和 $dis[k][j]$ 还没有被计算过的情况，那么，我们需要优化循环顺序，利用已经算过并且确定的点作为中介点，对其他点之间的最短路长都进行松弛。

考虑先循环 $k$ ，再循环 $i$ 和 $j$ ，发现这样就可以利用已有的结果进行松弛，那么，我们就得到了一个正确的循环顺序：先 $k$ 后 $i$ 、 $j$ 。

巧计方法：之所以 floyd 算法不是 Dijkstra 发明的，是因为他的名字是 $i$ 、 $j$ 、 $k$ ，而不是 $k$ 、 $i$ 、 $j$ 。

算法分析

优点

代码比较短，非常好写。
可以一次求出图中任意两点之间的最短路。
可以处理负边权问题。

缺点

效率较差，时间复杂度为 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。
代码可以优化的空间较小。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 405;
int g[N][N];
void floyd(int n) {
	for(int i=1;i<=n;++i) g[i][i]=0;
    //每个点到她本身的距离为 0，记得初始化
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
                //状态转移，注意循环顺序！
}
int main() {
	memset(g,0x3f,sizeof g); //全部初始化为 inf
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;++i) {
		int u,v,w;
		cin>>u>>v>>w;
		g[u][v]=w;
		g[v][u]=w; //如果是有向图，那么注释掉这一行
	} floyd(n);
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j)
			cout<<g[i][j]<<' ';
		cout<<'\n';
	}
	return 0;
}

最短路