版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
本节内容最短路径Floyd算法研/CSKAOYANRobertW．Floyd•
Floyd算法（Floyd-Warshall算法
）•
堆排序算法罗伯特·弗洛伊德（1936－2001）RobertW．Floyd1978年图灵奖得主研/CSKAOYANFloyd算法Floyd算法：求出每⼀对顶点之间的最短路径使⽤动态规划思想，将问题的求解分为多个阶段
对于n个顶点的图G，求任意⼀对顶点Vi—>Vj之间的最短路径可分为如下⼏个阶段：
#初始：不允他顶点中转，最短路径是？
#0：若允V0中转，最短路径是？
#1：若允V0、V1中转，最短路径是？
#2：若允V0、V1、V2中转，最短路径是？
…#n-1：若允V0、V1、V2……Vn-1中转，最短路径是？研/CSKAOYANFloyd算法⽬前来看，各V056V1顶点间的最短两个顶点之V0V0V1V2路径⻓度V0V1V2间的中转点-1-1-1A(-1)=V00613path(-1)=134V11004V1-1-1-1V2V25∞0V2-1-1-1#初始：不允他顶点中转，最短路径是？研/CSKAOYANFloyd算法⽬前来看，各V06V1顶点间的最短两个顶点之V2路径⻓度V0V1V2间的中转点V0V1134A(-1)=V00613path(-1)=V0-1-1-1V11004V1-1-1-15V25∞0V2-1-1-1V2#0：若允
V0
中转，最短路径是？——求
A(0)
和
path(0)若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]A(−1)[2][1]>A(−1)[2][0]+A(−1)[0][1]=11则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值A(0)[2][1]=11path(0)[2][1]=0;研/CSKAOYANFloyd算法⽬前来看，各V056V1顶点间的最短两个顶点之V2路径⻓度V0V1V2间的中转点V0V1-1A(-1)=V00613path(-1)=V0-1-1134V11004V1-1-1-1V2V25∞0V2-1-1-1#0：若允
V0
中转，最短路径是？——求
A(0)
和
path(0)V0V1V2V0V1V2若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]A(0)=V00613path(0)=V0-1-1-1则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
V11004V1-1-1-1path(k)[i][j]=k否则A(k)和path(k)保持原值V25110V2-10-1研/CSKAOYANFloyd算法⽬前来看，各V06V1顶点间的最短两个顶点之路径⻓度V0V1V2间的中转点V0V1V2134A(0)=V00613path(0)=V0-1-1-1V11004V1-1-1-15V2若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]V25110V2-10-1#1：若允V0、V1中转，最短路径是？——求
A(1)
和
path(1)A(0)[0][2]>A(0)[0][1]+A(0)[1][2]=10则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值A(1)[0][2]=10path(1)[0][2]=1;研/CSKAOYANFloyd算法⽬前来看，各V06V1顶点间的最短V0V1V2两个顶点之V0V1V2路径⻓度间的中转点5134A(0)=V00613path(0)=V0-1-1-1V11004V1-1-1-1V25110V2-10-1V2#1：若允V0、V1中转，最短路径是？——求
A(1)
和
path(1)V0V1V2V0V1V2若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]A(1)=V00610path(1)=V0-1-11则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
V11004V1-1-1-1path(k)[i][j]=k否则A(k)和path(k)保持原值V25110V2-10-1研/CSKAOYANFloyd算法⽬前来看，各V06V1顶点间的最短两个顶点之路径⻓度V0V1V2间的中转点V0V1V2134A(1)=V00610path(1)=V0-1-11V11004V1-1-1-15V2若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]V25110V2-10-1#2：若允V0、V1、V2
中转，最短路径是？——求
A(2)
和
path(2)A(1)[1][0]>A(1)[1][2]+A(1)[2][0]=9则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值A(2)[1][0]=9path(2)[1][0]=2;研/CSKAOYANFloyd算法⽬前来看，各V06V1顶点间的最短V0V1V2两个顶点之V0V1V2路径⻓度间的中转点5134A(1)=V00610path(1)=V0-1-11V11004V1-1-1-1V25110V2-10-1V2#2：若允V0、V1、V2
中转，最短路径是？——求
A(2)
和
path(2)V0V1V2V0V1V2若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]A(2)=V00610path(2)=V0-1-11则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
V1904V12-1-1path(k)[i][j]=k否则A(k)和path(k)保持原值V25110V2-10-1研/CSKAOYANFloyd算法⽬前来看，各V056V1顶点间的最短两个顶点之路径⻓度V0V1V2间的中转点V0V1V2134A(2)=V00610path(2)=V0-1-11V1904V12-1-1V2V25110V2-10-1从A(-1)和path(-1)
开始，经过n轮递推，得到A(n-1)和path(n-1)根据A(2)可知，V1到V2最短路径⻓度为4,若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]根据path(2)
可知，完整路径信息为V1_V2研/CSKAOYAN根据A(2)可知，V0到V2最短路径⻓度为10,则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
根据path(2)
可知，完整路径信息为V0_V1_V2path(k)[i][j]=k否则A(k)和path(k)保持原值根据A(2)可知，V1到V0最短路径⻓度为9,根据path(2)
可知，完整路径信息为V1_V2_V0Floyd算法核⼼代码V0V1V2V0V1V2V010V1A=V00613path=V0-1-1-16V11004V1-1-1-1134V25∞0V2-1-1-15V2若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
时间复杂度，O(|V|3)空间复杂度，O(|V|2)path(k)[i][j]=k否则A(k)和path(k)保持原值研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
0∞1∞
10V0
-1-1-1-1-1V01517V3A(-1)=V1
∞0∞15path(-1)=V1
-1-1-1-1-1V2
∞10∞7V2
-1-1-1-1-1V3
∞∞∞01V3
-1-1-1-1-1101V4
∞∞∞∞0V4
-1-1-1-1-1V4#初始：不允他顶点中转，最短路径是？研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
0∞1∞
10V0
-1-1-1-1-1V01517V3A(-1)=V1
∞0∞15path(-1)=V1
-1-1-1-1-1V2
∞10∞7V2
-1-1-1-1-1V3
∞∞∞01V3
-1-1-1-1-1101V4
∞∞∞∞0V4
-1-1-1-1-1V4#0：若允
V0
中转，最短路径是？——求
A(0)
和
path(0)若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值k=0研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
0∞1∞
10V0
-1-1-1-1-117A(-1)=V1
∞0∞15path(-1)=V1
-1-1-1-1-1V2
∞10∞7V2
-1-1-1-1-1V05V3
∞∞∞01V3
-1-1-1-1-1V4
∞∞∞∞0V4
-1-1-1-1-1101#0：若允
V0
中转，最短路径是？——求
A(0)
和
path(0)V41V3V0V1V2V3V4V0V1V2V3V4若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值V0
0∞1∞
10V0
-1-1-1-1-1A(0)=V1
∞0∞15path(0)=V1
-1-1-1-1-1V2
∞10∞7V2
-1-1-1-1-1V3
∞∞∞01V3
-1-1-1-1-1V4
∞∞∞∞0V4
-1-1-1-1-1研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
0∞1∞
10V0
-1-1-1-1-1V01517V3A(0)=V1
∞0∞15path(0)=V1
-1-1-1-1-1V2
∞10∞7V2
-1-1-1-1-1V3
∞∞∞01V3
-1-1-1-1-1101V4
∞∞∞∞0V4
-1-1-1-1-1V4#1：若允V0、V1中转，最短路径是？——求
A(1)
和
path(1)若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值k=1研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
0∞1∞
10V0
-1-1-1-1-1V01517V3A(0)=V1
∞0∞15path(0)=V1
-1-1-1-1-1V2
∞10∞7V2
-1-1-1-1-1V3
∞∞∞01V3
-1-1-1-1-1101V4
∞∞∞∞0V4
-1-1-1-1-1V4#1：若允V0、V1中转，最短路径是？——求
A(1)
和
path(1)A(0)[2][3]>A(0)[2][1]+A(0)[1][3]=2A(1)[2][3]=2若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值path(1)[2][3]=1;A(0)[2][4]>A(0)[2][1]+A(0)[1][4]=6A(1)[2][4]=6path(1)[2][4]=1;研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
0∞1∞
10V0
-1-1-1-1-117A(0)=V1
∞0∞15path(0)=V1
-1-1-1-1-1V2
∞10∞7V2
-1-1-1-1-1V05V3
∞∞∞01V3
-1-1-1-1-1V4
∞∞∞∞0V4
-1-1-1-1-1101#1：若允V0、V1中转，最短路径是？——求
A(1)
和
path(1)V41V3V0V1V2V3V4V0V1V2V3V4若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值V0
0∞1∞
10V0
-1-1-1-1-1A(1)=V1
∞0∞15path(1)=V1
-1-1-1-1-1V2
∞1026V2
-1-1-111V3
∞∞∞01V3
-1-1-1-1-1V4
∞∞∞∞0V4
-1-1-1-1-1研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
0∞1∞
10V0
-1-1-1-1-1V01517V3A(1)=V1
∞0∞15path(1)=V1
-1-1-1-1-1V2
∞1026V2
-1-1-111V3
∞∞∞01V3
-1-1-1-1-1101V4
∞∞∞∞0V4
-1-1-1-1-1#2：若允V0、V1、V2中转，最短路径是？——求
A(2)
和
V4path(2)若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值k=2研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
0∞1∞
10V0
-1-1-1-1-1V01517V3A(1)=V1
∞0∞15path(1)=V1
-1-1-1-1-1V2
∞1026V2
-1-1-111V3
∞∞∞01V3
-1-1-1-1-1101V4
∞∞∞∞0V4
-1-1-1-1-1#2：若允V0、V1、V2中转，最短路径是？——求
A(2)
和
V4path(2)A(1)[0][1]>A(1)[0][2]+A(1)[2][1]=2若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值A(2)[0][1]=2;path(2)[0][1]=2;A(1)[0][3]>A(1)[0][2]+A(1)[2][3]=3A(2)[0][3]=3;path(2)[0][3]=2;A(1)[0][4]>A(1)[0][2]+A(1)[2][4]=7A(2)[0][4]=7;path(2)[0][4]=2;研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
0∞1∞
10V0
-1-1-1-1-117A(1)=V1
∞0∞15path(1)=V1
-1-1-1-1-1V2
∞1026V2
-1-1-111V05V3
∞∞∞01V3
-1-1-1-1-1V4
∞∞∞∞0V4
-1-1-1-1-1101#2：若允V0、V1、V2中转，最短路径是？——求
A(2)
和
path(2)V41V3V0V1V2V3V4V0V1V2V3V4若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值V0
02137V0
-12-122A(2)=V1
∞0∞15path(2)=V1
-1-1-1-1-1V2
∞1026V2
-1-1-111V3
∞∞∞01V3
-1-1-1-1-1V4
∞∞∞∞0V4
-1-1-1-1-1研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
02137V0
-12-122V01517V3A(2)=V1
∞0∞15path(2)=V1
-1-1-1-1-1V2
∞1026V2
-1-1-111V3
∞∞∞01V3
-1-1-1-1-1101V4
∞∞∞∞0V4
-1-1-1-1-1#3：若允V0、V1、V2、V3中转，最短路径是？——求
A(3)
V4和
path(3)若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值k=3研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
02137V0
-12-122V01517V3A(2)=V1
∞0∞15path(2)=V1
-1-1-1-1-1V2
∞1026V2
-1-1-111V3
∞∞∞01V3
-1-1-1-1-1101V4
∞∞∞∞0V4
-1-1-1-1-1#3：若允V0、V1、V2、V3中转，最短路径是？——求
A(3)
V4和
path(3)A(2)[0][4]>A(2)[0][3]+A(2)[3][4]=4A(3)[0][4]=4;path(3)[0][4]=3;若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值A(2)[1][4]>A(2)[1][3]+A(2)[3][4]=2A(3)[1][4]=2;path(3)[1][4]=3;A(2)[2][4]>A(2)[2][3]+A(2)[3][4]=3A(3)[2][4]=3;path(3)[2][4]=3;研/CSKAOYANFloyd算法实例V11V2V0V1V2V3V4V0V1V2V3V4V0
02137V0
-12-12217A(2)=V1
∞0∞15path(2)=V1
-1-1-1-1-1V2
∞1026V2
-1-1-111V3
∞∞∞01V3
-1-1-1-1-1V05V4
∞∞∞∞0V4
-1-1-1-1-1101#3：若允V0、V1、V2、V3中转，最短路径是？——求
A(3)
和
path(3)V41V3V0V1V2V3V4V0V1V2V3V4若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值V0
02134V0
-12-123A(3)=V1
∞0∞12path(3)=V1
-1-1-1-13V2
∞1023V2
-1-1-113V3
∞∞∞01V3
-1-1-1-1-1V4
∞∞∞∞0V4
-1-1-1-1-1研/CSKAOYANFloyd算法实例1V117V2A(3)=V0V1V2V3V4path(3)=V0V1V2V3V4V0
02134V0
-12-123V1
∞0∞12V1
-1-1-1-13V2
∞1023V2
-1-1-113V3
∞∞∞01V3
-1-1-1-1-1V010511V3V4
∞∞∞∞0V4
-1-1-1-1-1V4#4：若允V0、V1、V2、V3、V4中转，最短路径是？——求
A(4)
和
path(4)若A(k−1)[i][j]>A(k−1)[i][k]+A(k−1)[k][j]则A(k)[i][j]=A(k−1)[i][k]+A(k−1)[k][j]；
path(k)[i][j]=k否则A(k)和path(k)保持原值k=4研/CSKAOYANFloyd算法实例1V117V2A(3)=V0V1V2V3V4path(3)=V0V1V2V3V4V0
02134V0
-12-123V1
∞0∞12V1
-1-1-1-13V2
∞1023V2
-1-1-113V3
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 昆虫绘画活动策划方案(3篇)
- 标签管理精准营销方案(3篇)
- 消防管网无水应急预案(3篇)
- 热力分配站施工方案(3篇)
- 生日活动粉丝策划方案(3篇)
- 石头店铺营销方案策划(3篇)
- 竹子探索活动方案策划(3篇)
- 绿化公司盆景营销方案(3篇)
- 良山铺子营销方案(3篇)
- 豆瓣小组引流营销方案(3篇)
- 感觉数学中的美
- 大型三维五轴光纤激光切割系统技术规范-征求意见稿
- 《肌张力障碍指南》课件
- 《事业编制人员入职信息填写表》
- 电气设备绝缘测量-课件
- 内蒙古生产建设兵团组建始末
- 桩基(预应力管桩)工程监理实施细则
- 《内河船舶法定检验技术规则》课件
- 知名房地产公司施工图设计技术指引
- 从报表看企业-2课件
- 产后康复骨盆修复
评论
0/150
提交评论