013--Floyd算法-动态规划-《算法设计技巧与分析》M.H.A学习笔记
多源最短路：有向图，求从每个顶点到其他所有顶点的最短距离。
基本思路：
假设有向图的所有点编号为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-1,i,j)，d(k-1,i,k)+d(k-1,k,j) } 1<=k<=n
于是我们有如下的递归式：
算法分析：
显然，Floyd算法的时间复杂度是Θ(n3)，空间复杂度是Θ(n2)。
伪代码：
C++代码：
for( int k = 1; k <= n; ++k )
for( int i = 1; i <= n; ++i )
for( int j = 1; j <= n; ++j )
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);- 顶
- 0
- 踩
- 0
软件工程阅读排行
-
2014-10-15
-
2016-06-06
-
2013-05-06
-
yershop商城系统开发一——thinkphp和onethink简析
2016-06-08
-
013--Floyd算法-动态规划-《算法设计技巧与分析》M.H.A学习笔记
2016-06-28
-
解决Visual Studio 2010下TFS服务无法连接问题
2014-05-30
-
2016-06-06
-
2013-05-06
最新文章
-
2022-03-16
-
2022-03-16
-
2022-03-16
-
Redis之RedisTemplate配置方式(序列和反序列化)
2022-03-16
-
2022-03-16
-
2022-03-16
-
2022-03-16
-
2019-07-10
热门源码
