1 / 16
文档名称:

算法12-最短路径-弗洛伊德(Floyd)算法.ppt

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

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

分享

预览

算法12-最短路径-弗洛伊德(Floyd)算法.ppt

上传人:165456465 2025/3/15 文件大小:6.54 MB

下载得到文件列表

算法12-最短路径-弗洛伊德(Floyd)算法.ppt

相关文档

文档介绍

文档介绍:该【算法12-最短路径-弗洛伊德(Floyd)算法 】是由【165456465】上传分享,文档一共【16】页,该文档可以免费在线阅读,需要了解更多关于【算法12-最短路径-弗洛伊德(Floyd)算法 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。1

方法一:每次以一个顶点为源点,重复执行Dijkstra算法n次—— T(n)=O(n³)
方法二:弗洛伊德(Floyd)算法
单击此处添加文本具体内容,简明扼要地阐述你的观点。单击此处添加正文,文字是您思想的提炼,请尽量言简意赅的阐述观点。
:已知一个各边权值均大于0的带权有向图,对每一对顶点 vi  vj,要求求出vi 与vj之间的最短路径和最短路径长度。
2
:逐个顶点试探法
求最短路径步骤
初始时设置一个n阶方阵,令其对角线元素为0,若存在弧<Vi,Vj>,则对应元素为权值;否则为
逐步试着在原直接路径中增加中间顶点,若加入中间点后路径变短,则修改之;否则,维持原值
所有顶点试探完毕,算法结束
,假设求顶点Vi到Vj的最短路径。如果从Vi到Vj有弧,[i][j]的路径,但该路径是否一定是最短路径,还需要进行n次试探。
第一次,判别( Vi, V0 )和( V0,Vj ),即判别(Vi, V0 , Vj)是否存在,若存在,则比较( Vi, Vj )和(Vi, V0 , Vj)的长度,取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。
第三次,再加一个顶点V2,继续进行试探。
第二次,再加一个顶点V1,如果(Vi, … , V1) 和(V1, … , Vj)分别是当前找到的中间顶点序号不大于0的最短路径,那么(Vi, … , V1, … , Vj )就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj之间顶点序号不大于0的最短路径相比较,取较短者为从Vi到Vj的中间顶点序号不大于1的最短路径。
V2
V3
V0
V1
1
2
3
4
5
6
8
9
0 1 2 3
0
1
2
3
0 1 2 4
0 0 9 2
3 5 0 8
0 1 6 0
8
8
8
8
D(-1) =
D(-1)为有向网的邻接矩阵
第一步:以D(-1)为基础,以V0为中间顶点,求从Vi到Vj的最短路径。该路径或者为从Vi到Vj的边, 或者为(Vi,V0)+(V0,Vj) 。
D(0) [i][j] =
min{D(-1) [i][j], D(-1) [i][0]+D(-1) [0][j]}
4
7
D(0) =
D(0) [i][j] 为从Vi到Vj的中间顶点序号不大于0的最短路径长度.
V0
V2
V3
V0
V1
1
2
3
4
5
6
8
9
以D(0)为基础,以V1为中间顶点,求从Vi,到Vj的最短路径。该路径或者为从Vi到Vj的边, 或者为从Vi开始通过V0或V1到达Vj的最短路径 。
D(1) [i][j] =
min{D(0) [i][j], D(0) [i][1]+D(0) [1][j]}
0 1 2 3
0
1
2
3
0 1 2 4
0 0 9 2
3 5 0 8
0 1 6 0
8
8
8
8
A(-1) =
4
7
D(0) =
10
3
6
D(1) =
V0
V1
V0
V1
V2
V3
V0
V1
1
2
3
4
5
6
8
9
以D(1)为基础,以V2为中间顶点,求从Vi,到Vj的最短路径。或者为从Vi到Vj的边, 或者为从Vi开始通过V0,V1, V2到达Vj的最短路径 。
D(2) [i][j] =
min{D(1) [i][j], D(1) [i][2]+D(1) [2][j]}
0 1 2 3
0
1
2
3
0 1 2 4
0 0 9 2
3 5 0 8
0 1 6 0
8
8
8
8
A(-1) =
4
7
A(0) =
10
3
6
D(1) =
D(2) =
12
9
10
V0
V1
V2
0 1 2 3
0
1
2
3
0 1 2 4
0 0 9 2
3 5 0 8
0 1 6 0
8
8
8
8
A(-1) =
4
7
A(0) =
10
3
6
A(1) =
D(2) =
12
9
10
D(3) =
V2
V3
V0
V1
1
2
3
4
5
6
8
9
以D(2)为基础,以V3为中间顶点,求从Vi,到Vj的最短路径。或者为从Vi到Vj的边, 或者为从Vi开始通过V0,V1, V2,V3到达Vj的最短路径 。
D(3) [i][j] =
min{D(2) [i][j], D(2) [i][3]+D(2) [3][j]}
9
11
8
V3
V2
V0
V1
D(3) [i][j] 即为从Vi到Vj的最短路径长度.
9
A
C
B
2
6
4
3
11
0 4 11
6 0 2
3  0
初始:
路径:
AB AC
BA BC
CA
0 4 6
6 0 2
3 7 0
加入B:
路径:
AB ABC
BA BC
CA CAB
0 4 11
6 0 2
3 7 0
加入A:
路径:
AB AC
BA BC
CA CAB
0 4 6
5 0 2
3 7 0
加入C:
路径:
AB ABC
BCA BC
CA CAB
例题:
10

A
C
B
2
6
4
3
11
初始:
0 4 11
6 0 2
3  0
length=
0 1 1
2 0 2
3 0 0
path=
加入A:
0 4 11
6 0 2
3 7 0
length=
0 1 1
2 0 2
3 1 0
path=
加入B:
0 4 6
6 0 2
3 7 0
length=
0 1 2
2 0 2
3 1 0
path=
加入C:
0 4 6
5 0 2
3 7 0
length=
0 1 2
3 0 2
3 1 0
path=

最近更新

心理测量在人力资源管理中的应用培训课件 92页

冷硬呋喃树脂砂工艺性能的试验研究 2页

2025年人体动脉结构与功能详解 13页

2025年专业护理服务礼仪规范解读 73页

再生水成本管理探讨—以北京某公司为例 2页

内交联型高吸水性树脂的合成及性能研究 2页

2025年下肢脉管炎治疗与护理实战解析 15页

关于辽宁省金县铸造厂“财政包干”若干问题的.. 2页

关于漆树实行以林养林对策及措施的思考 2页

关于柴油离心沉淀计算方法的讨论 2页

关于改革外汇留成制度问题的探讨 2页

关于推进企业发展的市场导向问题研究 2页

关于感生电动势和动生电动势问题的讨论 2页

2025年砂磨机合作协议书 65页

2025年矿山施工设备:凿岩机械合作协议书 57页

2025年电泳设备项目发展计划 51页

2025年玻璃钢复合材料项目建议书 54页

关于宽幅织机的经济效果及其最佳筘幅值的探讨.. 2页

关于外板余量布置图的编制和应用 2页

《学法指导讲座》 40页

2025年淋巴瘤患者自疗攻略与自我护理要点 36页

2025年抗生素使用指南与常见药物解析 25页

工程质量控制中试验检测的重要性 24页

2级经销商分销协议 5页

2024年高中生情绪调控心得体会(热门24篇) 36页

【2023年】福建省龙岩市辅警协警笔试笔试真题.. 16页

村后备干部笔试试题A及答案(最新版) 12页

物理学英文论文 4页

电工安全教育考试题 3页

QR6.2-02目标分解及指标计划 4页