C++ 图论之Floyd算法求解次最短路径的感悟，一切都是脱壳后找最值而已

一枚大果壳

发布于 2023-12-10 15:01:20

1440

发布于 2023-12-10 15:01:20

文章被收录于专栏：编程驿站编程驿站

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;
}

测试结果：