013--Floyd算法-动态规划-《算法设计技巧与分析》M.H.A学习笔记

多源最短路：有向图，求从每一个顶点到其他所有顶点的最短距离。

基本思路：

假定有向图的所有点编号为1到n，l[i,j]表示从i到j的边的长度，如果不存在边，则置为正无穷。

定义d(k,i,j)表示从点i到点j，并且不经过编号大于k的点的最短距离。

初始化条件：

K=0时，d(0,j)=l[i,j]。

状态转移方程：

d(k,j)=min{ d(k⑴,j)，d(k⑴,k)+d(k⑴,k,j) }   1<=k<=n

因而我们有以下的递归式：

算法分析：

明显，Floyd算法的时间复杂度是Θ(n³)，空间复杂度是Θ(n²)。

伪代码：

C++代码：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!