【图论C++】Floyd算法（多源最短路径长 及 完整路径）

>>>竞赛算法

/*** @file            * @author          jUicE_g2R(qq:3406291309)————彬(bin-必应)*						一个某双流一大学通信与信息专业大二在读	* * @brief           一直在算法竞赛学习的路上* * @copyright       2023.9* @COPYRIGHT			 原创技术笔记：转载需获得博主本人同意，且需标明转载源** @language        C++* @Version         1.0还在学习中  */

• UpData Log👆 2023.9.29 更新进行中
• Statement0🥇 一起进步
• Statement1💯 有些描述可能不够标准，但能达其意

21 Floyd算法

21-1 比较几种求解 最短路径 的算法

• 常见的有：DJ算法、Floyd算法、A*算法、Bellman-Ford 算法、SPFA算法

其中 A*算法 是 DJ算法 的plus版，SPFA算法 是 Bellman-Ford 算法的plus版

算法名称	DJ算法	Floyd算法	SPFA算法	A*算法
单/多源	单源	多源		单源
可否求负权值图	否	可		否
效率	较高	较低		很高
思想	贪心	动规DP，松弛	松弛	启发式搜索，估值函数
解的最优性	最优	最优		相对最优

• 单源指的是：一个起点，到其他所有点

21-2 孕育出 Floyd算法 的 原因

求 n个端点的图 的 多源最短路径，可以将 Dijkstra算法 执行 n次，但这样时间复杂度也上去了$O(n^2\ast n)$，而且代码也很臃肿，此时就需要针对这类问题单独设计一种算法解决 代码量大 的问题——就产生了Floyd算法 。

虽然 Floyd算法 的效率相对较低${}^1$且不适合处理数据量过大${}^2$的图 ，但是它处理 稠密图${}^3$ 时效率是高于 Dijkstra算法的，而且 floyd算法 的代码量极小${}^4$，实现也很简单！！！

${}^1$：时间复杂度为 $O(n^3)$。

${}^2$：空间复杂度为 $O(n^2)$：，使用的是邻接矩阵（直接开辟二维数组）。在处理稠密图时格外浪费空间。

${}^3$：由于三重循环结构紧凑

${}^4$：Dijkstra算法的思想上是很容易接受的，但是实现上其实是非常麻烦的

21-3 Floyd算法 的 实现

• 第一步：存储图：使用的是领接矩阵

• 第二步：三重循环

设 $m$ 为中介点、$i$ 为起点、$j$ 为终点，这一点很像 A*算法。

判断由 $起点i$ 直接到 $终点j$ 的代价值 是否大于 $起点i$ 经由 $中介点m$ 到 $终点j$ 的代价值（即判断 $dp[i][j]>dp[i][m]+dp[m][j]$），若大于（判断成立）则将从 $起点i$ 直接到 $终点j$ 的代价值 更新为 $dp[i][j]=dp[i][m]+dp[m][j]$

//法一：三目运算符直接搞定
dp[i][j] = dp[i][j] > (dp[i][m]+dp[m][j])  ?  (dp[i][m]+dp[m][j]) : dp[i][j];
//法二：调用函数
dp[i][j] = min(dp[i][j], (dp[i][m]+dp[m][j]));

三重循环结束后，路径规划结束。

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int dp[6][6]={{  0,   2,   3,   6, INF, INF}, 				{  2,   0, INF, INF,   4,   6}, 				{  3, INF,   0,   2, INF, INF},				{  6, INF,   2,   0,   1,   3}, {INF,   4, INF,   1,   0, INF}, 			{INF,   6, INF,   3, INF,   0}
};
vector<vector<int>> Mid(6,vector<int>(6,INF));
char ch[6]={'A','B','C','D','E','F'};
void Floyd(int n){int m,i,j;for(m=0; m<n; m++)                                      //k为中介点for(i=0; i<n;i++) 			                        //i为起点for(j=0; j<n;j++){ 		                        //j为终点if(dp[i][j] > (dp[i][m]+dp[m][j])){         //松弛操作dp[i][j] = (dp[i][m]+dp[m][j]);Mid[i][j]=m;                            //记录中介点}}
}
void Find_Path(int i, int j){if(Mid[i][j]==INF)cout<< ch[i];else{Find_Path(i, Mid[i][j]);i=Mid[i][j];while(Mid[i][j]!=INF){cout<< "->" << ch[ Mid[i][j] ] ;i=Mid[i][j];}}cout<< "->" << ch[j] <<endl;
}
int main(void){int n=6;Floyd(n);for(int i=0; i<n; i++){for(int j=0; j<n; j++){cout<< "结点" << ch[i] << "到结点" << ch[j] <<"的最短路径长为：" << dp[i][j] << ",";cout<<"最短路径为：";Find_Path(i,j);}cout<<endl;}return 0;
}

就纯一暴力法，没什么说的