1 / 11
文档名称:

最短路径Dijkstra算法.ppt

格式:ppt   大小:362KB   页数:11页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

最短路径Dijkstra算法.ppt

上传人:幻影 2021/11/17 文件大小:362 KB

下载得到文件列表

最短路径Dijkstra算法.ppt

相关文档

文档介绍

文档介绍:最短路径Dijkstra算法
2020/12/2
1
1 最短路径
两点之间的最短路径问题:
求从某个源点到其余各点的最短路径
每一对顶点之间的最短路径
2020/12/2
2
精品资料
3
你怎么称呼老师?
如果老师最后没有总结一节课的重点的难点,你是否会认为老师的教学方法需要改进?
你所经历的课堂,是讲座式还是讨论式?
教师的教鞭
“不怕太阳晒,也不怕那风雨狂,只怕先生骂我笨,没有学问无颜见爹娘 ……”
“太阳当空照,花儿对我笑,小鸟说早早早……”
4
求从源点到其余各点的最短路径的算法的基本思想:
依最短路径的长度递增的次序求得各条路径
源点
v1
v2

其中,从源点到顶点v的最短路径是所有最短路径中长度最短者。
2020/12/2
5
2 Dijkstra算法
单源最短路径问题是:
给定带权的有向图G=(V,E),源点v∈V,求从v到V中其余各顶点的最短路径。
如何求解上图中的最短路径问题,Dijkstra提出了一种解决方案。
2020/12/2
6
即迪杰斯特拉算法,其基本思想如下:
设置辅助数组Dist,其中每个分量Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径的长度。
1)在所有从源点出发的弧中选取一条权值最小的弧,即为第一条最短路径。
V0和k之间存在弧
V0和k之间不存在弧
2020/12/2
7
3)每次从集合V-S中取出具有最短特殊路径长度的顶点u,将u加到S中,同时对数组Dist做必要的修改。若 Dist[u]+[u][k]<Dist[k]
则将 Dist[k] 改为 Dist[u]+[u][k]。
其中,特殊路径指从源点到u中间只经过S中顶点的路径。
2)设置一个顶点集合S,存放最短路径的终点。顶点k为当前最短路径的终点,将Vk 加入集合S中,而Dist[k]为最短路径的长度。
4) 重复操作2)、3)共n-1次。由此求得图上其余各顶点的最短路径是依路径长度递增的序列。
2020/12/2
8
若带权图G如下所示,根据上述算法来求解源点v0到v2的最短路径。
2020/12/2
9
根据以上分析和举例,不难得出狄杰斯特拉算法,其描述如下:
Void shortestPath(MGraph G,int V0, PathMatrix &P, ShortPathTable &D)
//P[v]表示最短路径,D[v]表示带权长度
//P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点
//final[v]为TRUE,即已经求得从v0到v的最短路径
{ for(v=0;v<;v++){
final[v]=FALSE;
D[v]=[v0][v];
for(w=0;w<;w++) P[v][w]=FALSE;//设置空路径
if(D[v]<INFINTY){P[v][v0]=TRUE;p[v][v]=TRUE;}
}
2020/12/2
10

最近更新

CE-158在PC-1500机的传输应用 2页

2025年工厂品保工作心得 22页

BW-1变稳飞机飞行品质试验研究 2页

BP神经网络优化槐花中芦丁的提取工艺 2页

2025年工作车位出租合同模板怎么写 12页

AYX-3型调压积时式采样器通过技术鉴定 2页

2025年工作总结 2025初中班主任年终工作总结范.. 24页

杭州官方版房屋买卖合同样本 5页

AP-脱脂剂用于猪皮、绵羊大油板皮脱脂的探索 2页

AGFA CR系统影像伪影及解决对策 2页

高性能混凝土运输及配送服务协议书(2025年度.. 9页

2025年岗位工作调动申请书(精选篇) 14页

801胶在低压电器线圈上的应用 2页

2025年山西考研网上报名什么时候截止 4页

东陂长汀品唇鳅的个体生物学初步研究 2页

660 MW机组FCB试验转速飞升异常分析及处理 2页

600MW锅炉节油燃烧器改造措施探讨 2页

水产加工废渣清运合同 9页

橡胶制品液碱运送协议 9页

2025年山东服装职业学院2025单招和综合评价招.. 2页

2025年山东开学交通安全第一课心得及启迪(最.. 16页

500A1200V可控硅元件管芯部分试制工艺 2页

2025年山东中小学生2025寒假放假时间 7页

2025年山东2025年下半年中小学教资面试报名时.. 6页

服装店转让正式合同书范本 6页

2024年《国有企业管理人员处分条例》测试题【.. 15页

浙教版小学四年级2022-2023学年劳动与技术教学.. 37页

2025年玉米烘干厂可行性报告模板 31页

驻村干部年度组织生活会个人对照检查材料 5页

医学伦理知情同意书 3页