随州市住房和城乡建设部网站,广告营销手段有哪些方式,一级a做爰片免费网站丶,云主机安装网站竞赛算法 /*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * brief 一直在算法竞赛学习的路上* * copyright 2023.9* COPYRIGHT 原创技术笔记#xff… 竞赛算法 /*** 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 4Dijkstra算法的思想上是很容易接受的但是实现上其实是非常麻烦的 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]));三重循环结束后路径规划结束。 #includebits/stdc.h
using namespace std;
const int INF0x3f3f3f3f;
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}
};
vectorvectorint Mid(6,vectorint(6,INF));
char ch[6]{A,B,C,D,E,F};
void Floyd(int n){int m,i,j;for(m0; mn; m) //k为中介点for(i0; in;i) //i为起点for(j0; jn;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]);iMid[i][j];while(Mid[i][j]!INF){cout - ch[ Mid[i][j] ] ;iMid[i][j];}}cout - ch[j] endl;
}
int main(void){int n6;Floyd(n);for(int i0; in; i){for(int j0; jn; j){cout 结点 ch[i] 到结点 ch[j] 的最短路径长为 dp[i][j] ,;cout最短路径为;Find_Path(i,j);}coutendl;}return 0;
}就纯一暴力法没什么说的
