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年度工业用气体环保政策研究与应用合同 9页

实用的高中叙事作文集合5篇 10页

对学校工作的意见和建议(12篇) 24页

小学叙事作文(集合15篇) 17页

2025年度小学校园绿化租赁养护合同 8页

2025年度小产权房购房合同解除及终止协议模板.. 7页

2025年度家长与学生生活自理能力培养协议 8页

幼儿园小班上学期教学工作计划(8篇) 25页

2025年度家政服务人员劳动合同与薪酬福利标准.. 8页

2025年度家庭财产分割夫妻自愿离婚协议 7页

教师节表彰个人主要事迹材料(3篇) 10页

2025年度家具板材加工与绿色家居设计理念合作.. 9页

春季中心幼儿园学期园务工作计划(28篇) 117页

2025年度室内外装修拆除工程保险合同深度解析.. 8页

2025年度实习生实习期间实习成果展示合同 9页

2025年度宅基地使用权转让协议书(专业版)—.. 8页

2025年度学校代课教师教学研究与创新合同 9页

2025年度婚庆礼仪服务与培训合同 9页

中考考前心理辅导课件 75页

水产冷链运输合同模板3篇 55页

气体类危险品运输合同范例3篇 48页

森林公园修缮工程合同3篇 51页

校园雕塑制作安装合同3篇 51页

艺术舞蹈老师简历模板 1页

服装设计合作协议书 5页

煤炭资源地质勘查设计编写提纲 14页

硫酸铵生产硫酸钾的可行性方案 31页