>>>竞赛算法
/**
* @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 比较几种求解 最短路径 的算法
- 21-2 孕育出 Floyd算法 的 原因
- 21-3 Floyd算法 的 实现
- 就纯一暴力法,没什么说的
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
∗
n
)
O(n^2*n)
O(n2∗n),而且代码也很臃肿,此时就需要针对这类问题单独设计一种算法解决 代码量大 的问题——就产生了Floyd算法
。
虽然 Floyd算法
的效率相对较低
1
^1
1且不适合处理数据量过大
2
^2
2的图 ,但是它处理 稠密图
3
^3
3 时效率是高于 Dijkstra算法
的,而且 floyd算法
的代码量极小
4
^4
4,实现也很简单!!!
1 ^1 1:时间复杂度为 O ( n 3 ) O(n^3) O(n3)。
2 ^2 2:空间复杂度为 O ( n 2 ) O(n^2) O(n2):,使用的是邻接矩阵(直接开辟二维数组)。在处理
稠密图
时格外浪费空间。3 ^3 3:由于三重循环结构紧凑
4 ^4 4:
Dijkstra算法
的思想上是很容易接受的,但是实现上其实是非常麻烦的
21-3 Floyd算法 的 实现
- 第一步:存储图:使用的是领接矩阵
- 第二步:三重循环
设 m m m 为中介点、 i i i 为起点、 j j j 为终点,这一点很像 A*算法。
判断由 起点 i 起点i 起点i 直接到 终点 j 终点j 终点j 的代价值 是否大于 起点 i 起点i 起点i 经由 中介点 m 中介点m 中介点m 到 终点 j 终点j 终点j 的代价值(即判断 d p [ i ] [ j ] > d p [ i ] [ m ] + d p [ m ] [ j ] dp[i][j]>dp[i][m]+dp[m][j] dp[i][j]>dp[i][m]+dp[m][j]),若大于(判断成立)则将从 起点 i 起点i 起点i 直接到 终点 j 终点j 终点j 的代价值 更新为 d p [ i ] [ j ] = d p [ i ] [ m ] + d p [ m ] [ j ] dp[i][j]=dp[i][m]+dp[m][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]));
三重循环结束后,路径规划结束。文章来源:https://www.uudwc.com/A/LaWro/
文章来源地址https://www.uudwc.com/A/LaWro/
#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;
}