




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
图算法(二)最短路经ShortestPath青岛理工大学acm2023/2/51Dijkstra算法练习题链接/vjudge/contest/view.action?cid=29337#overviewFloyd算法练习题链接/vjudge/contest/view.action?cid=29305#overview密码都是:6712023/2/52/sjjg/DataStructure/DS/web/flashhtml/Dijkstra.htm这个链接是Dijskra算法的动态演示2023/2/53问题:两地之间是否有通路?若存在多条通路,哪条路最短?最短路径问题2023/2/54单源最短路径
Single-SourceShortestPath(Dijkstra算法)所有顶点对间的最短路径问题
All-PairsShortestpaths
(Floyd算法)
最短路径问题2023/2/55单源最短路径
Single-SourceShortestPath问题:带权有向图G(E,V),找出从给定源顶点s到其它顶点v的权最小路径。
“最短路径”=最小权路径的权是路径上所有边的权之和。例:道路图:从青岛理工到金沙滩的最短路径?2023/2/56v5v4v01005601010v1v2v3205030图中从v0到其余各顶点之间的最短路径:v0到v1无
v0到
v2(v0,v2)10v0到
v3(v0,v4,
v3)50v0到
v4(v0,v4)30v0到
v5(v0,v4,
v3,v5)60单源最短路径2023/2/57贪心算法:
若顶点序列{V0,V1,…,Vn}是从V0到Vn的最短路,则序列{V0,V1,…,Vn-1}必为从V0到Vn-1的最短路。权非负的单源最短路径算法(Dijkstra)2023/2/58基本思想:将图中所有顶点分成两组:S,V-S
一组是包括已确定最短路径的顶点的集合S,另一组是尚未确定的最短路径的顶点集V-S。
S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。权非负的单源最短路径算法(Dijkstra)2023/2/59权非负的单源最短路径算法(Dijkstra)
初始时,S仅包含源v0,
特殊路径:
从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。步骤:(1)取v0加入S中
(2)从V-S中取出具有当前最短路径长度的顶点w加入S中。2023/2/510v5v4v0100601010v1v3205030v2v0
v1
v2
v3
v4
v5v0
v1
v2
v3
v4
v5权非负的单源最短路径算法(Dijkstra)邻接矩阵2023/2/511v0到其它各点的最短路
i=1i=2i=3i=4i=5初始时v0∞10∞30100v2∞10∞30100v4∞10503090v3∞30503060v5∞30503060v1∞305030602023/2/512Dijkstra算法:一般情况下,Dist[k]=<源点到顶点i的弧上的权值>
或者=<源点到其它顶点的路径长度>+<其它顶点到顶点i的弧上的权值>
设置辅助数组Dist,其中每个分量Dist[i]表示
当前所求得的从源点到其余各顶点i的最短路径的长度。2023/2/5131)在所有从源点出发的弧中选取一条权值最小的弧,即为第一条最短路径。2)修改其它各顶点的Dist[i]值。假设求得最短路径的顶点为u,若Dist[u]+G.arcs[u][i]<Dist[i]则将Dist[i]改为Dist[u]+G.arcs[u][i]V0和i之间存在弧V0和i之间不存在弧其中的最小值即为最短路径的长度。2023/2/514权非负的单源最短路径算法(Dijkstra)#include<iostream>#include<string.h>#include<stdio.h>usingnamespacestd;constintINF=0xfffffff;#definemaxn110int
grap[maxn][maxn];//邻接矩阵存储图int
pre[maxn];//标记这个点是否已经被选过intn,m;int
dist[maxn];//记录从源点到其他所有点的最短距离2023/2/515voidinit()//对一些数据进行初始化{inti,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
grap[i][j]=INF;
memset(pre,0,sizeof(pre));}voiddijkstra(intu){
inti,j;
for(i=1;i<=n;i++)//首先求出源点到其他所有点的距离
dist[i]=grap[u][i];
pre[u]=1;2023/2/516
intx=u;
for(i=1;i<n-1;i++) {int
maxs=INF;
for(j=1;j<=n;j++)//类似于最小生成树prim算法,找到距离最短的那个点
if(!pre[j]&&maxs>dist[j]) {
maxs=dist[j]; x=j; }
pre[x]=1;
for(j=1;j<=n;j++)//然后再通过这个点去得到其他点的最短距离
if(!pre[j]&&dist[j]>(dist[x]+grap[x][j])&&grap[x][j]<INF)
dist[j]=grap[x][j]+dist[x]; }}2023/2/517intmain(){
scanf("%d%d",&n,&m); init();
inti,x,y,z;
for(i=0;i<m;i++)//对有向图进行存储
{
scanf("%d%d%d",&x,&y,&z);
grap[x][y]=z; } dijkstra(1);//假设求点1到其他点的最短路
return0;}2023/2/518所有顶点对之间的最短路径算法Floyd算法已知一个有向图(无向图),对于每对顶点Vi!=Vj
,求出它们之间的最短路径长度。解决这个问题有两种方法:(1)轮流以每个顶点为源点重复执行dijkstra算法。(2)采用Floyd算法,时间复杂度O(n3)
2023/2/519例13226431104116023∞
0初始a:P=000000046602370a2=0411602370k=1a1=k=2k=30465023700-10P1=000000010002000010002300010P2=P3=a3=Floyd算法演示2023/2/520Floyd算法描述定义一个n阶的方阵序列:A(-1),A(0)A(1)……A(n-1),其中:A(-1)[i][j]表示顶点vi到vj的直接边长,A(-1)就是存储图的邻接矩阵Edge[n][n]A(0)[i][j]表示从顶点vi到vj,中间顶点是v0的最短路径长度A(1)[i][j]表示从顶点vi到vj,中间顶点序号不大于1的最短路径长度………..A(k)[i][j]表示从顶点vi到vj,中间顶点序号不大于k的最短路径长度..........2023/2/521A(n-1)[i][j]是最终求得的从顶点vi到vj的最短路径长度增加中间顶点vk后,对于图中的每一对顶vi和vj,要比较从vi到vk的最短路径长度加上从vk到vj的最短路径长度是否小于原来从vi到vj的最短路径长度,即比较A(k-1)[i][k]+A(k-1)[k][j]与A(k-1)[i][j]的大小,去较小的为A(k-1)[i][j]的值。因此我们得到递推公式为:2023/2/522Floyd算法的代码实现#include<iostream>#include<string.h>#include<stdio.h>#include<algorithm>#include<queue>usingnamespacestd;constintINF=0xfffffff;#definemaxn110int
grap[maxn][maxn];//邻接矩阵存储图intn,m;int
dist[maxn][maxn];//记录从所有点之间的最短距离2023/2/523voidinit()//对一些数据进行初始化{inti,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
grap[i][j]=INF;}voidfloyd(){inti,j,k;
for(i=1;i<=n;i++)//初始化,一开始每个点与点之间的路径长度就等于grap中的长度
for(j=1;j<=n;j++)
dist[i][j]=grap[i][j];
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) {if(k==i||k==j)continue;
if(dist[i][k]+dist[k][j]<dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j]; }}2023/2/524intmain(){
scanf("%d%d",&n,&m); init();
inti,x,y,z
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2025学年甘肃省天水市一中高三收心考试语文试题含解析
- 江西丰城市第二中学2024-2025学年高三下学期开学考试英语试题含解析
- 新乡职业技术学院《中外幼教名著选读》2023-2024学年第二学期期末试卷
- 重庆移通学院《水上运动》2023-2024学年第一学期期末试卷
- 石家庄铁道大学《生物学综合实验》2023-2024学年第二学期期末试卷
- 2025年山东省泰安九中高三下学期第一次模拟考试科历史试题试卷含解析
- 巴音郭楞蒙古自治州和静县2025年数学四年级第二学期期末质量检测试题含解析
- 2025年保安证考试竞争分析试题及答案
- 华东师范大学《数值计算与机器人应用》2023-2024学年第二学期期末试卷
- 2025年保安证考试技巧分享及试题及答案
- 危险作业监护人资格考试
- 合同协议公司员工聘用合同7篇
- 2025年XX县社会工作部工作计划
- 2025年安徽卫生健康职业学院单招职业适应性测试题库含答案
- 2025年安徽电子信息职业技术学院单招职业倾向性考试题库新版
- 2025年常州信息职业技术学院单招职业技能考试题库审定版
- 2025上海崇明现代农业园区开发限公司招聘39人易考易错模拟试题(共500题)试卷后附参考答案
- 老年肺炎临床诊断与治疗专家共识(2024年版)解读
- 4.1 人要有自信 (课件)2024-2025学年七年级道德与法治下册(统编版2024)
- 护理随访案例分享课件
- 天然产物药物生物合成
评论
0/150
提交评论