当前位置: 首页 > news >正文

门户网站建设依据今日头条网站推广

门户网站建设依据,今日头条网站推广,手机浏览微网站,有哪些做的好的网站>>>竞赛算法 /*** 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(n2n),而且代码也很臃肿,此时就需要针对这类问题单独设计一种算法解决 代码量大 的问题——就产生了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]));

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

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

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

http://www.shuangfujiaoyu.com/news/20886.html

相关文章:

  • 企业建设网站费用百度技术培训中心
  • 提升网站流量的方法新闻实时报道
  • 网站不备案可以做微信小程序么获客软件排名前十名
  • 网站建设网络推广书生长春百度网站优化
  • 网页设计作业网站素材和效果图百度搜索 手机
  • 公司设计图平面百度seo搜索营销新视角
  • 大兴网站开发网站建设价格合肥关键词排名技巧
  • wordpress seo怎么做搜索引擎优化策略应该包括
  • 成品网站建设价格百度问一问在线咨询客服
  • 设计开发评审报告seo排名平台
  • 优秀购物网站建设谷歌seo和百度seo区别
  • 甘肃兰州怎么样网络舆情优化公司
  • 那网站做问答移动排名提升软件
  • 济南网站建设首选传承网络品牌推广策略与方式
  • 做网站这么做哪里注册域名最便宜
  • 珠海做网站费用新软件推广平台
  • 帝国和织梦哪个做网站好seo工具查询
  • 微信网站如何做网络推广竞价是什么
  • 导航网站开发工具怎么让网站快速收录
  • 东城响应式网站建设营销策略有哪些
  • 做网站设计的提成点是多少360竞价推广登录入口
  • 一个独立IP做几个网站比较合适怎么做网络营销推广
  • 用discuz做的网站广州广告公司
  • 廊坊建设部网站网页
  • pc网站开发微信支付媒体代发网站
  • 大学关工委加强自身建设网站宣传营销顾问
  • 杭州网站建设 巴零网站seo搜索引擎优化怎么做
  • 网站建设工作进度域名备案查询系统
  • 企业网站备案座机号搜索引擎排名google
  • 单页的网站怎么做的常用的网络推广的方法有哪些