算法最短路径弗洛伊德Floyd算法学习教案

1、会计学1算法算法(sun f)最短路径弗洛伊德最短路径弗洛伊德Floyd算法算法(sun f)第一页，共16页。 1.第一次，判别（ Vi, V0 ）和（ V0，Vj ），即判别(Vi, V0 , Vj）是否存在(cnzi)，若存在(cnzi)，则比较（ Vi, Vj ）和(Vi, V0 , Vj）的长度，取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。第2页/共16页第二页，共16页。 2 . 第 二 次 ， 再 加 一 个 顶 点 V 1 ， 如 果(rgu)(Vi, , V1） 和(V1, , Vj）分别是当前找到的中间顶点序号不大于0的最短路径，那么(Vi, , V1, ,

2、 Vj ）就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj之间顶点序号不大于0的最短路径相比较，取较短者为从Vi到Vj的中间顶点序号不大于1的最短路径。 3. 第三次，再加一个顶点V2，继续进行(jnxng)试探。 第3页/共16页第三页，共16页。V2V3V0V1123456890 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 8888D(-1) = D(-1)为有向网的邻接矩阵 第一步:以D(-1)为基础，以V0为中间顶点(dngdin)，求从Vi到Vj的最短路径。该路径或者为从Vi到Vj的边, 或者为(Vi,V0

3、)+(V0,Vj) 。 D(0) ij = minD(-1) ij, D(-1) i0+D(-1) 0j47D(0) = D(0) ij 为从Vi到Vj的中间顶点(dngdin)序号不大于0的最短路径长度.V0第4页/共16页第四页，共16页。V2V3V0V112345689 以D(0)为基础，以V1为中间顶点，求从Vi,到Vj的最短路径。该路径或者为从Vi到Vj的边, 或者为从Vi开始通过(tnggu)V0或V1到达Vj的最短路径 。 D(1) ij = minD(0) ij, D(0) i1+D(0) 1j0 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6

4、 0 8888A(-1) =47D(0) =1036D(1) =V0V1V0V1第5页/共16页第五页，共16页。V2V3V0V112345689 以D(1)为基础，以V2为中间顶点，求从Vi,到Vj的最短路径。或者为从Vi到Vj的边, 或者为从Vi开始(kish)通过V0,V1, V2到达Vj的最短路径 。 D(2) ij = minD(1) ij, D(1) i2+D(1) 2j0 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 8888A(-1) =47A(0) =1036D(1) =D(2) =12 910V0V1V2第6页/共16页第六页，共16

5、页。0 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 8888A(-1) =47A(0) =1036A(1) =D(2) =12 910D(3) =V2V3V0V112345689 以D(2)为基础，以V3为中间顶点，求从Vi,到Vj的最短路径。或者为从Vi到Vj的边, 或者为从Vi开始(kish)通过V0,V1, V2,V3到达Vj的最短路径 。 D(3) ij = minD(2) ij, D(2) i3+D(2) 3j 9 11 8V3V2V0V1 D(3) ij 即为从Vi到Vj的最短路径(ljng)长度.第7页/共16页第七页，共16页。8ACB

6、2643110 4 116 0 23 0初始：初始：路径：路径：AB ACBA BCCA0 4 66 0 23 7 0加入加入B：路径：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入加入A：路径：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入加入C：路径：路径：AB ABCBCA BCCA CAB例题例题(lt)：第8页/共16页第八页，共16页。9例例ACB264311初始：初始：0 4 116 0 23 0length=0 1 12 0 23 0 0path=加入加入A：0 4 116 0 23 7 0length=0 1 12 0

7、23 1 0path=加入加入B：0 4 66 0 23 7 0length=0 1 22 0 23 1 0path=加入加入C：0 4 65 0 23 7 0length=0 1 23 0 23 1 0path=第9页/共16页第九页，共16页。10证明：归纳证明，始归纳于证明：归纳证明，始归纳于s (s (上角上角标标););(1) (1) 归纳基础：当归纳基础：当s=-1 s=-1 时，时， A(-1) A(-1) ij= Edgeij, vi ij= Edgeij, vi 到到vj , vj , 不经过任何顶点的边，是最短路不经过任何顶点的边，是最短路径。径。(2)(2)归纳假设：当归

8、纳假设：当sksk时，时， A(s) A(s) ijij是从顶点是从顶点vi vi 到到vj , vj , 中间中间顶点的序号不大于顶点的序号不大于s s的最短路径的的最短路径的长度长度(chngd);(chngd);(3)(3)当当s=ks=k时，时，第10页/共16页第十页，共16页。11ijkA(k-1) ikA(k-1) kjA(k-1) ij第11页/共16页第十一页，共16页。12图用邻接矩阵存储图用邻接矩阵存储edge 存放最短路径长度存放最短路径长度(chngd)pathij是从是从Vi到到Vj的最短路径上的最短路径上Vj前一顶点序号前一顶点序号5.算法算法(sun f)实现实

9、现void floyd ( ) for ( int i = 0; i n; i+ ) /矩阵矩阵dist与与path初始化初始化 for ( int j = 0; j n; j+ ) /置置A(-1) distij = Edgeij; pathij = -1; / 初始不经过初始不经过(jnggu)任何顶点任何顶点 for ( int k = 0; k n; k+ ) /产生产生dist(k)及及path(k) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if (distik + distkj distij ) distij = distik +

10、 distkj; pathij = k; /缩短路径缩短路径, 绕过绕过 k 到到 j / floyd 第12页/共16页第十二页，共16页。136.6.算法分析算法分析(fnx)(fnx)： 设最内层循环体为基本操作，算法有三层循环，每层循环设最内层循环体为基本操作，算法有三层循环，每层循环n n次，所以次，所以T(n)=O(n3)T(n)=O(n3)第13页/共16页第十三页，共16页。14 A(-1) A(0) A(1) A(2) A(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 4 0 1 4 0 1 10 3 0 1 10 3 0

11、1 9 3 1 0 9 2 0 9 2 0 9 2 12 0 9 2 11 0 8 2 2 3 5 0 8 3 4 0 7 3 4 0 6 3 4 0 6 3 4 0 6 3 6 0 6 0 6 0 9 10 6 0 9 10 6 0 Path(-1) Path(0) Path(1) Path(2) Path(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 3 1 1 0 0 1 1 0 0 1 1 0 0 1 1 2 0 1 1 2 0 3 1 2 2 2 0 2 2 0 0 0

12、 2 0 0 1 2 0 0 1 2 0 0 1 3 0 0 3 0 0 0 3 0 0 0 3 0 2 0 3 0 2 0 3 0第14页/共16页第十四页，共16页。15 A(-1) A(0) A(1) A(2) A(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 4 0 1 4 0 1 10 3 0 1 10 3 0 1 9 3 1 0 9 2 0 9 2 0 9 2 12 0 9 2 11 0 8 2 2 3 5 0 8 3 4 0 7 3 4 0 6 3 4 0 6 3 4 0 6 3 6 0 6 0 6 0 9 10 6 0 9 10 6 0 Path(-1) Path(0) Path(1) Path(2) Path(3) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0