C++ 图论之Floyd算法求解次最短路径的感悟，一切都是脱壳后找最值而已-摩杜云开发者社区

公众号：编程驿站

1. 前言

抛开基因的影响，学霸和学渣到底是在哪一点上有差异？

学霸刷完 200 道题，会对题目分类，并总结出解决类型问题的通用模板，我不喜欢模板这个名词，感觉到投机的意味，或许用方法或通用表达式更高级一点。而事实上模板一词更准确。

每一道题目在描述时，会套上一堆场景说词，可以说是契合真正的应用领域，或者说是出题人的故弄玄虚，弄了一些花里胡哨的迷糊你的外表，这时考核的不是专业知识，而是语文阅读能力。一旦脱出外壳，露出来的底层需求，就是书本上最基础的知识。

小学生学乘法表后，老师会布置很多应用题，不管应用题目的描述如何变化，一旦语文阅读理解过关，剩下的就是套用九九乘法表。为什么学霸学起来一直很轻松原因就在这里，做道时看山不是山。而学渣总是认为一道题目就是一个新知识，疲于学习，永无止境地追赶，停留在看山是山的境界。

为什么说这些？

这段时间写最小生成树、次最小生成树以及最短路径和次最短路径。总结一下，应该不难发现。本质就是在群体数据中找最小值和次最小值，这是最最基础的最值算法思想。如果是在一维数组中找最大值、最小值，只要有点语言基础的都能解决。

代码结构如下：

#include <bits/stdc++.h>
using namespace std;
int main() {
	//一维数组
	int nums[5]= {5,3,1,8,2};
	//存储最大值
	int maxVal_1=nums[0];
	//存储最小值
	int maxVal_2=nums[0];
	//遍历数组
	for(int i=0; i<5; i++) {
		//是否大于最大值
		if( nums[i]>maxVal_1 ) {
			//原来的最大值必然退居成第二大值
			maxVal_2=maxVal_1;
			//如果大于最大值，必然成为最大值
			maxVal_1=nums[i];
		} else if(nums[i]>maxVal_2) {
			//如果大于第二大的值，成为第二大值。
			maxVal_2=nums[i];
		}
	}
	cout<<maxVal_1<<"\t"<<maxVal_2<<endl;
	return 0;
}

其中玄机很简单。公司里空降了一位新领导，如果级别比现任的最高领导的级别高。则现任最高领导成为二把手，新领导成为一把手。如果新领导只比公司现任的二把手高，则挤掉二把手，成为新的二把手。

找最值算法本质，确定一个值，然后查找是否有比此值更大或更小的值，多重选择而已。

当问题变成找最小生成树，次最小生成树、最短路径，次最短路径时……

算法的思想本质没有发现变化，只是遍历的对象变成了图结构或树结构。虽然算法的底层策略不变，但因图结构比线性结构复杂的多，遍历过程中面临的选择也增多，如何选择，如何存储就变得稍难一点。

最短路径常用的算法为Floyd、Bellman、SPFA、Dijkstra。既然能找出最短路径，当然是能找出次最短路径的。下面将分别使用Floyd算法，细聊如何找出次最短路径。

2. `Floyd`算法

对Floyd算法不甚了解的读者可以查阅本公众号里的《C++图论之常规最短路径算法的花式玩法（Floyd、Bellman、SPFA、Dijkstra算法合集）》一文。

使用Floyd算法求解最短路径时，顺手也能求解出次最短路径，下面捋捋这个过程。以下面的图结构为案例。

邻接矩阵存储存初始时，节点之间的权重关系。0表示自己和自己的距离，INF表示两节点间无直接连接，数值表示两节点的连接权重。Floyd是多源最短路径算法。算法结果需要记录任意两点间的距离，二维数组是较佳的选择。

现在除了要求解最短路径，还需要求解出次最短路径。则有两种存储方案：

三维数组。
两个二维数组。

三维数组本质是多个二维数组在空间深度上的叠加。如下图，所有二维数组的i和j坐标描述任意两个节点的编号。z坐标表示两个节点之间的第一最短距离、第二最短距离、第三最短距离……

演示算法流程时，借助于两个二维数数组更易于表达。如下图所示，初始，最短距离为两点间的权重值，次最短距离为INF（无穷大）。

Tips：次最短距离有严格次最短距离，要求次最短距离必须小于最短距离。非严格次最小距离，则可以是大于或等于最短距离。

Floyd算法的特点是通过在任意两点间插入一个节点，检查是否能缩短其距离。如选择节点1做为中插入点，检查其它任意点之间是否可以通过此点缩短其距离。

graph_1[3][4]原来的值为INF，经过中转点后值为graph_1[3][1]+graph_1[1][4]=10，大于原来的最短距离，则原来的最短距离变成第二短距离，经过中转后的值为新的最短距离。

以此类推，分别计算出其它两点经过1号节点后的最短距离和次最短距离。

如3-5原来最短距离是1，如果经过1号节点则距离为graph_1[3][1]+graph_[1][5]=12。大于原始值但是小于次最短距离，故，最短距离不更新，次最短距离更新为12。

一维数组中的选择是线性的，图结构中的选择复杂。Floyd算法提供插入这个选择理念，底层最值的算法思想没有发生任何本质上的变化。新老大了，原老大退居第二；新老二来了，原老二退居第三……

其它演示流程不再展现，直接上代码。

#include <bits/stdc++.h>

using namespace std;
//最短路径
int graph_1[100][100][2];
map<pair<int,int>,vector<int>> paths;
//节点数、边数
int n,m;
//无穷大
const int INF=999;
//初始化图，自己和自己的距离为0，和其它节点距离为 INF
void init() {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i==j) {
				graph_1[i][j][0]=0;
				graph_1[i][j][1]=0;
			} else {
				graph_1[i][j][0]=INF;
				graph_1[i][j][1]=INF;
			}
		}
	}
}

//交互式得到节点之间关系
void read() {
	int f,t,w;
	for(int i=1; i<=m; i++) {
		cin>>f>>t>>w;
		graph_1[f][t][0]=w;
		//无向图
		graph_1[t][f][0]=w;
	}
}
//Floyd算法
void  floyd() {
	//核心代码
	for(int dot=1; dot<=n; dot++) {
		//以每一个点为插入点，然后更新图中任意两点以此点为中转时的路线权重
		for(int  i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				//经过中转后的权重是否小于原来权重
				if( graph_1[i][dot][0]+graph_1[dot][j][0] <graph_1[i][j][0]  ) {

					graph_1[i][j][1]=graph_1[i][j][0];
					graph_1[i][j][0] =graph_1[i][dot][0]+graph_1[dot][j][0];

				} else if(  graph_1[i][dot][0]+graph_1[dot][j][0]>graph_1[i][j][0] &&    graph_1[i][dot][0]+graph_1[dot][j][0] <graph_1[i][j][1]  ) {
						graph_1[i][j][1]=graph_1[i][dot][0]+graph_1[dot][j][0];

				}
			}
		}
	}
}
//输入矩阵中信息
void show() {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++)
			cout<<graph_1[i][j][0]<<"-"<<graph_1[i][j][1]<<"\t";
		cout<<endl;
	}
}

int main(int argc, char** argv) {
	cin>>n>>m;
	init();
	read();
	floyd();
	show();
	return 0;
}

测试数据：

测试结果：

有问题的代码

如图所示，1-3的最短距离是4，直观可以判断正确性。但是1-3的次最短距离是6，可能会让你有点莫名其妙。因为直观上讲，应该是9，也就1-5-3这条路径，除此之外，似乎没有比这个值更合理的。

6这个值是怎么来的？

算法的计算逻辑是把1-3的路径分解成1-5和3-5，因1-5的之间的最短路径是1-3-5值为5。所以，最后的结果是1-5的最短路径值加上3-5之间的最短路径值，结果为6。如下图演示效果。

如何解决这个问题？

先跑一次Floyd算法，得到任意两点间的距离，再删除任意两点之间的最短路径上的边，再跑一次Floyd算法，便可求解出次最短路径。

如在求解1-2的最短路径时，记录最短路径的整个路径链1-3-5-2，然后试着删除1-3跑一次，再删除3-5跑一次，再删除5-2走一次，最后在三次中选择最1-2之间的最短距离。

代码如下：

#include <bits/stdc++.h>
using namespace std;
//图
int graph[100][100];
//最短路径
int paths[100][100];
//节点数、边数
int n,m;
//记录任意两点间最短距离所比对过的节点
map<pair<int,int>,vector<int>> prec;
//无穷大
const int INF=999;
//初始化图，自己和自己的距离为0，和其它节点距离为 INF
void init() {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i==j)graph[i][j]=paths[i][j]=0;
			else graph[i][j]=paths[i][j]=INF;
		}
	}
}
//交互式得到节点之间关系
void read() {
	int f,t,w;
	for(int i=1; i<=m; i++) {
		cin>>f>>t>>w;
		graph[f][t]=paths[f][t]=w;
		//无向图
		graph[t][f]=paths[t][f]=w;
	}
}
//Floyd 最短路径算法
void  floyd() {
	//核心代码
	for(int dot=1; dot<=n; dot++) {
		//以每一个点为插入点，然后更新图中任意两点以此点为中转时的路线权重
		for(int  i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				//经过中转后的权重是否小于原来权重
				if( paths[i][dot]+paths[dot][j] <paths[i][j]  ) {
					paths[i][j] =paths[i][dot]+paths[dot][j];
					//记录任意两点之间的节点
					pair<int,int> p= {i,j};
					vector<int> v=prec[p];
					v.push_back(dot);
					prec[p]=v;
				}
			}
		}
	}
}
//次最短路径算法
void floyd(int i,int j) {
	//恢复图原来数据
	for(int i1=1; i1<=n; i1++) {
		for(int j1=1; j1<=n; j1++) {
			paths[i1][j1]=graph[i1][j1];
		}
	}
	//删除最短路径上的边
	paths[i][j]=INF;
   //路一次算法
	for(int dot=1; dot<=n; dot++) {
		//以每一个点为插入点，然后更新图中任意两点以此点为中转时的路线权重
		for(int  i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				//经过中转后的权重是否小于原来权重
				if( paths[i][dot]+paths[dot][j] <paths[i][j]  ) {
					paths[i][j] =paths[i][dot]+paths[dot][j];
				}
			}
		}
	}
}

//输出矩阵中信息
void show() {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++)
			cout<<paths[i][j]<<"\t";
		cout<<endl;
	}
}

int main(int argc, char** argv) {
	cin>>n>>m;
	init();
	read();
	floyd();
	show();

	int i=1,j=2;
	cin>>i>>j;
	int i1=i;
	pair<int,int> p= {i,j};
	vector<int> v=prec[p];
	int res=INF;
	for(int k=0; k<v.size(); k++) {
		floyd(i1,v[k]);
		res=min(res,paths[i][j]);
		i1=v[k];
	}
	floyd(i1,j);
	res=min(res,paths[i][j]);
	cout<<i<<"-"<<j<<" "<<res<<endl;
	return 0;
}

测试1-2之间的最短路径。

时间复杂度分析：一句话，时间复杂度有点感人，性能堪忧，至于如何优化就留给聪明的你了。

3. 最小环

图中最小环的问题，可以使用Floyd算法求解。算法流程：

跑一次算法，得到任意两点间的最短距离。
检查任意两点之间的最短距离是否有其它节点存在(环至少需要 3 个点)，如这两点之间有连接，可证明这两点间有环。
求解最小环。

如下图所示，1-2之间的最短路径链为1-3-5-2。因为1-2之间没有直接相连的边，说明这个最短路径不构成环。3-2最短路径线为3-5-2，且3-2之间有边相连，证明2-5-3这条最短路径存在环，且此环的权重和为10；如1-5的最短距离为1-3-5，且是一个环，权重和为13。至于最小环是谁，只有找出所有环且计算它们的权重和后方可知。

编码实现：

#include <bits/stdc++.h>

using namespace std;
//图
int graph[100][100];
//最短路径
int paths[100][100];
//节点数、边数
int n,m;
//记录任意两点间最短距离所比对过的节点
map<pair<int,int>,vector<int>> prec;
//无穷大
const int INF=999;
//初始化图，自己和自己的距离为0，和其它节点距离为 INF
void init() {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i==j)graph[i][j]=paths[i][j]=0;
			else graph[i][j]=paths[i][j]=INF;
		}
	}
}

//交互式得到节点之间关系
void read() {
	int f,t,w;
	for(int i=1; i<=m; i++) {
		cin>>f>>t>>w;
		graph[f][t]=paths[f][t]=w;
		//无向图
		graph[t][f]=paths[t][f]=w;
	}
}
//Floyd算法 最短路径算法
void  floyd() {
	//核心代码
	for(int dot=1; dot<=n; dot++) {
		//以每一个点为插入点，然后更新图中任意两点以此点为中转时的路线权重
		for(int  i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				//经过中转后的权重是否小于原来权重
				if( paths[i][dot]+paths[dot][j] <paths[i][j]  ) {
					paths[i][j] =paths[i][dot]+paths[dot][j];
					//记录
					pair<int,int> p= {i,j};
					vector<int> v=prec[p];
					v.push_back(dot);
					prec[p]=v;
				}
			}
		}
	}
}
//找最小环
int calMinCircle() {

	int minCircle=INF;

	for(int  i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			pair<int,int> p= {i,j};
			vector<int> v=prec[p];
			if(v.size()==0)continue;
			//确定是不是环
			if( graph[i][j]!=INF ) {
                //找最小环
				minCircle=min(minCircle,paths[i][j]+graph[i][j] );
			}
		}
	}
	return minCircle;
}

//输出矩阵中信息
void show() {
	for(int i=1; i<=n; i++) {
		for(int j=i+1; j<=n; j++)
			cout<<paths[i][j]<<"\t";
		cout<<endl;
	}
}

int main(int argc, char** argv) {
	cin>>n>>m;
	init();
	read();
	floyd();
	//show();
	int res= calMinCircle();
	cout<<res;
	return 0;
}

测试结果：

如果是有向图，需要注意方向。如下图，2-3-5之间没有环，唯一的环是1-3-5。

４．总结

本文讲解了如何使用｀Floyd｀算法求解次最短路径.

1. 前言

2. Floyd算法

3. 最小环

４．总结

2. `Floyd`算法