1 / 16
文档名称:

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

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

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

分享

预览

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

上传人:h377683120 2020/11/20 文件大小:1.06 MB

下载得到文件列表

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

文档介绍

文档介绍:算法12--最短路径--弗洛伊德(Floyd)算法
*
求最短路径步骤
初始时设置一个n阶方阵,令其对角线元素为0,若存在弧<Vi,Vj>,则对应元素为权值;否则为
逐步试着在原直接路径中增加中间顶点,若加入中间点后路径变短,则修改之;否则,维持原值
所有顶点试探完毕,算法结束
3. Floyd算法思想:逐个顶点试探法
,假设求顶点Vi到Vj的最短路径。如果从Vi到Vj有弧,[i][j]的路径,但该路径是否一定是最短路径,还需要进行n次试探。
,判别( Vi, V0 )和( V0,Vj ),即判别(Vi, V0 , Vj)是否存在,若存在,则比较( Vi, Vj )和(Vi, V0 , Vj)的长度,取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。
2. 第二次,再加一个顶点V1,如果(Vi, … , V1) 和(V1, … , Vj)分别是当前找到的中间顶点序号不大于0的最短路径,那么(Vi, … , V1, … , Vj )就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj之间顶点序号不大于0的最短路径相比较,取较短者为从Vi到Vj的中间顶点序号不大于1的最短路径。
3. 第三次,再加一个顶点V2,继续进行试探。
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

最近更新

风成岩层分布特征-全面剖析 27页

算机网络故障诊断与维护 31页

家装建材网店装修合同3篇 50页

家庭装修服务协议范本3篇 53页

面向未来城市的智能交通网络设计-全面剖析 24页

跨域数据融合技术研究-全面剖析 25页

2025年小学教师读书笔记心得3篇 14页

2025年小学教师教学个人期末总结 30页

2025年小学学校毛笔书法教学计划 12页

餐饮特许经营合同范本 6页

餐厅排烟系统安装合同范本 12页

2025年小学六年级庆祝国庆节手抄报作品一等奖.. 8页

鸡的常见疾病及综合防治 18页

2025年小学入学自我介绍范文 3页

高校“化学实验安全”课程混合式教学探索 35页

进口叉车购销协议 6页

2025年小学五年级数学教学工作计划 12页

高中美术 古希腊、罗马美术和文艺复兴美术教学.. 39页

购销合同中的物流与配送条款 5页

2025年小学二年级主题班会方案设计方案5篇 14页

黑龙江生物竞赛试题及答案 4页

外研社版小学三年级下册英语知识点汇总(精) 5页

食品安全自查、从业人员健康管理、进货查验记.. 9页

人教版五年级数学下册第一二单元测试卷 5页

劳动保护用品专项检查总结 8页

陕旅版小学英语五年级下册教学计划教学进度安.. 6页

电解槽制作安装施工方案 23页

苗木验收单2 2页

高速公路隧道贯通施工专项方案 63页

“一病一优”优质护理服务模式的应用效果分析.. 3页