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页

毕业生就业基地合同及见习生合作条款 7页

步行街运营承包合同 6页

正式合同模板:代课教师聘用 6页

棉花购销及加工合同 6页

中国历史上锡箔的特殊用途和传统制作工艺 2页

中、高碳钢钢球生产工艺及经济效益 2页

《快乐生活-快乐工作》 59页

不锈钢圆筒形中温黑体炉的研究 2页

上钢一厂摆式飞剪剪切机构的探讨 2页

上海城市交通 水质问题及对策 2页

上市公司会计信息失真的原因及对策研究 2页

三芯扇形纸力缆中二维电场分布的有限元素法分.. 2页

2025年幼儿园感恩节系列活动总结 11页

2025年幼儿园小班艺术领域活动方案创意方案大.. 9页

一类新型相变,一种新的软化工艺 2页

一种稻壳基蓝藻处理剂及其制备方法 2页

一种新型的气动伺服阀及其在位置控制系统中的.. 2页

机场扩建土方运输项目合同3篇 54页

服装辅料干线物流合同3篇 55页

有机溶剂运输合同样本3篇 54页

时尚家居店装修合同协议书3篇 55页

旅游景区石材采购协议样本3篇 59页

1.6-微积分基本定理-人教a版高中数学选修2-2课.. 31页

医院后勤人员工作计划范文与医院后勤安全工作.. 15页

区委科技局干部年底述职总结与区委经济审计学.. 8页

借款合同模板(电子版) 5页

2024河南电工技师考试题库电工证考试试题及答.. 59页

历年山东省烟台市物业公司物业管理基本工作范.. 15页

电线送检委托书 4页