文档介绍：该【算法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=