首页 / 算法 / 图论——Floyd算法拓展及其动规本质
图论——Floyd算法拓展及其动规本质
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了图论——Floyd算法拓展及其动规本质,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2648字,纯文字阅读大概需要4分钟。
内容图文
![图论——Floyd算法拓展及其动规本质](/upload/InfoBanner/zyjiaocheng/756/cb43f030bcd64e05afbab56f79c49ef0.jpg)
一、Floyd算法本质
首先,关于Floyd算法:
Floyd-Warshall算法是一种在具有正或负边缘权重(但没有负周期)的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度(加权)。
通俗一点说,Floyd就是可以用于求解多源汇最短路径的算法,也就是求连通图中任意两点间的最短路径,当然,如果不连通,它返回的就是无穷大(初始化为无穷大)。Floyd可以处理负权,但无法处理有负权环的图。
接下去进入正题:
众所周知,Floyd算法本质其实是动态规划。它其实是由三维数组的DP优化而来。
我们用数组dis[i,j,k]表示从点i到点j,以前k个点作为中转点的最短路径长度。
为了实现状态转移,我们把当前dis[i,j,k]的所有状态的集合划分为两类,一类是经过k点的,一类是不经过k点的。对于前者,显然dis[i,j,k]=dis[i,j,k-1];对于后者,我们可以得到dis[i,j,k]=dis[i,k,k-1]+dis[k,j,k-1],也就是i到k的最短路径长度加上k到j的最短路径长度。于是我们便可以得到状态转移方程:
dis[i,j,k] = min(dis[i,j,k-1],dis[i,k,k-1]+dis[k,j,k-1]
边界条件:dis[i,j,0] = w[i,j],即i与j之间的直接边的权值,若不存在则为正无穷;还有dis[i,i,0]=0。
代码如下:
void floyd_original() { for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { dis[i][j][k]=min(dis[i][j][k-1],dis[i][k][k-1]+dis[k][j][k-1]); } } } }
类比前面背包问题的优化方式,我们发现对于每一层k,它的状态计算只与第k-1层的状态有关,那么我们便可以省略这一维。因为省略之后,在计算第k层的dis[i,j]时,我们所需的dis[i,k]和dis[k,j]还是上一层的。
这一点用一个式子便可证明:
dis[i,k,k] = min(,dis[i,k,k-1] dis[i,k,k-1]+dis[k,k,k-1]) = min(dis[i,k,k-1], d[i,k,k-1]+0) = d[i,k,k-1]
dis[k,j]同理即可得证。
于是我们便可得到最普遍的二维数组的状态转移方程:
dis[i,j] = min(dis[i,j],dis[i,k]+dis[k,j])
从三维变成二维确实降低了空间开销,但是我们也可以发现时间复杂度是不变的,仍然是O(n³)。
二、Floyd算法变形解决有边数限制的最短路问题
我们用三维数组d[i,j,e]表示点i到点j,经过e条边的最短路径长度。
我们假设经过的倒数第二个点是k,那么我们很容易就可以得到状态转移方程:
d[i,j,e]=min{d[i,k,e-1]+w[k,j]} k∈[1,n]
代码如下:
for(int e=1;e<=n;e++) for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j][e]=min(d[i][j][e],d[i,k,e-1]+w[k][j]);
但是这样处理的时间复杂度高达O(n4),于是我们自然会想到要做一些优化。
我们为了达到明显的指数级别的优化效果,我们选择二进制优化。
假设限制的边数为s时,我们把第三维e表示成2e条边。那么我们预处理时只需要将2e<k的所有符合条件的e枚举完即可。然后便可以用若干个2的整数次幂的和表示出s。
我们再用数组f[i,j,t]来表示状态,其中t表示边数为前t个2的整数次幂的和,那么我们就可以得到状态转移方程:
f[i,j,t] = min{f[i,k,t-1]+d[k,j,t]}
其中k是i到j的最短路径中间经过的一个点,将路径中所有的边划分为前20+21+…+2t-1条与后2t条。
那么我们就只需在最外层枚举k即可。这个算法的时间复杂度就可以降低到O(n3logn)。
大家对这个问题有兴趣的话可以去看一下这道题:POJ 3613
内容总结
以上是互联网集市为您收集整理的图论——Floyd算法拓展及其动规本质全部内容,希望文章能够帮你解决图论——Floyd算法拓展及其动规本质所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。