多源最短路:有向图,求从每一个顶点到其他所有顶点的最短距离。
假定有向图的所有点编号为1到n,l[i,j]表示从i到j的边的长度,如果不存在边,则置为正无穷。
定义d(k,i,j)表示从点i到点j,并且不经过编号大于k的点的最短距离。
K=0时,d(0,i,j)=l[i,j]。
d(k,i,j)=min{ d(k⑴,i,j),d(k⑴,i,k)+d(k⑴,k,j) } 1<=k<=n
因而我们有以下的递归式:
明显,Floyd算法的时间复杂度是Θ(n3),空间复杂度是Θ(n2)。