3弗洛伊德算法.ppt

文档介绍：弗洛伊德算法
弗洛伊德算法
弗洛伊德算法简介
弗洛伊德算法基本思想
弗洛伊德算法举例
练习

简介：
弗洛伊德算法又称距离矩阵法，是由弗洛伊德（）在1962年研究出的一种算法
特点：
可以求出图中路段带有负路权时的最短路
　可以求任意两点间的最短路

(1)给出网络的邻接矩阵D，令D(0)=D,其元素为dij(0)

v1
V3
V4
V2
2
6
1
8
4
图1

(2)在原路径里增加一个新结点，如果产生的新路径比原路径更小，则用新路径值代替原路径的值。这样依次产生n个矩阵（n为网络结点数）
用公式表示就是，对于K=1,2,3…n,第k个矩阵
运算过程中K从1开始，而i,j 则分别从1到n取遍所有值，然后k加1，直到k等于n时停止。

见word

见word