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=

最近更新

2025年度房地产教育培训年售房委托协议 9页

2025年度户外活动场地保洁与环保服务合同 9页

2025年度店铺入股文化体验店合作开发协议 7页

2025年度幼儿园租赁合同风险评估与预防 8页

2025年度年劳动合同法版网络安全服务合同 9页

2025年度工程预付款保证金合同范本 7页

2025年度工厂设备知识产权转让合同 9页

2025年度工业用地买卖合同正式版 9页

实用的周记高中作文汇总5篇 7页

2025年度展会专业观众邀请与合作合同 8页

小学开幕式作文(4篇) 5页

幼儿园上学期大班班主任工作总结(3篇) 9页

幼儿教师述职报告范文(素材稿件12篇) 37页

担保书范文(29篇) 43页

春节的作文[锦集15篇] 16页

有关护士辞职报告(28篇) 33页

2025年度实习生合同汇编:网络安全领域实习生.. 8页

2025年度安全生产安全生产培训及考核合同 8页

2025年度学生实习就业实习补贴及福利协议书 7页

2025年度学历合同中介服务合作协议 9页

汽车展厅装修合同范本3篇 52页

2025年度农村集体果树资源整合与收益共享合同.. 8页

水库加固工程物料运输合同3篇 50页

水上乐园改造合同范本3篇 50页

橡胶制品运输合同模板3篇 48页

桥梁工程设计居间合同3篇 51页

杭州市剧场租赁合同3篇 49页

新青岛版数学三年级下第3单元-两位数乘两位数.. 14页

中兴天翼手机汇编 29页

知识竞赛颁奖大会上的主持词 3页