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=

最近更新

三峡工程导流及施工通航方案研究 2页

2025年幼儿园年度工作总结 7页

2025年幼儿园小班经典数学智力题集锦分享 4页

2025年幼儿园小班个人工作总结示例 16页

一种预测电解加工阳极形状的方法 2页

2025年幼儿园实习生个人工作总结00字精选 28页

一种耐高温抗光辐射的隔热涂料设计探讨 2页

一种测定真丝绸练白质量的简易方法 2页

一种新型漂浮式波浪能发电装置的设计与研究 2页

人教版六年级数学上册期末测试卷(新版) 6页

机床设备居间协议样本3篇 50页

机场周边房产居间协议样本3篇 49页

木制品包装材料运输合同3篇 50页

服装成衣运输合同模板3篇 53页

服装企业办公楼装修合同3篇 53页

早教中心股权转让居间合同3篇 46页

旅游景区贷款居间合同样本3篇 51页

旅游大巴司机劳务合同3篇 48页

人教版五年级数学上册期末考试卷(1套) 6页

MOOC 计算机组成与CPU设计实验-江苏大学 中国.. 100页

2022年如何解决问题发现和问题分析的七个步骤.. 35页

小学“全国防灾减灾日”ppt 28页

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

服装设计合作协议书 5页

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

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

2022年首都经济贸易大学工商管理专业《管理学.. 22页

学生5mm坐标纸(虚线 word版)直接打印 2页

(完整版)天津大学非线性信息处理技术 12页

中式烹调工艺 2页