注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

极夜.潜的博客

 
 
 

日志

 
 

Floyd算法——任意两点间最短路径的动态规划算法  

2011-06-09 13:43:48|  分类: Algorithm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Floyd算法是寻找加权图(权值可为负)中任意两个结点间最短路径的算法。Floyd算法的基本思想:两结点间的最短路径要么是相邻时最短,要么是以通过几个中间结点为跳板时距离最短。算法每次以其中一个结点为跳板,如果以该结点为跳板后两结点间路径缩短,则更新这两结点间的路径。算法执行|V|次结束,直到测试完每个充当跳板的结点。

若用Dijkstra算法计算任意两点间的最短路径,需要执行|V|次,且图中含有负权值时不能用Dijkstra算法。Floyd算法只能求出两点间最短路径的长度,无法得到这条最短路径,当然,如果记录了每步更新所经过的中间结点,仍可通过回溯得到两点间的最短路径。

一、任意两点间最短路径的Floyd算法

Floyd算法采用邻接矩阵W作为图的存储结构,W[i,j]表示结点vi和vj之间的距离(权重);D(k)记录经历k步后,两点间的路径长,k=0, ..., n (n = |V|),初始时,W=D(0);P记录每步更新时结点间经历的中间结点,通过对P矩阵的回溯操作,可得两点间的最短路径,初始时,P为0矩阵。

算法第k步的更新规则:以结点k为跳板,测试通过该结点后,两点间距离是否缩短,若距离不缩短则保留k-1步的结果,D(k)[i,j]= D(k-1)[i,j],若距离缩短则更新两点间的距离,D(k)[i,j]= D(k-1)[i,k]+ D(k-1)[k,j],也就是,D(k)[i,j]= min{D(k-1)[i,j], D(k-1)[i,k]+ D(k-1)[k,j]},由此可见,Floyd算法是典型的动态规划算法。如果第k个结点对缩短vi和vj间的路径做出贡献,P[i,j]=k。

  Floyd算法——任意两点间最短路径的动态规划算法 - 极夜.潜 - 极夜.潜的博客

由于程序中矩阵D(k)无后效性,实际只用一个矩阵D即可,而不需要n+1个矩阵D(k)。

二、Floyd算法实例

用Floyd算法求含负权值的有向图中任意两点间的最短路径,图G及算法初始状态(D(0)=W,P=0)如下所示:
  Floyd算法——任意两点间最短路径的动态规划算法 - 极夜.潜 - 极夜.潜的博客

为方便查看,标记浅蓝色的行列是在更新过程中实际参与计算的元素,显然标蓝的元素在该步更新中不会被改变。每步中P中的元素由0变为结点编号,意味着该结点的加入会缩短其行列对应的两个结点间的路径。如第1步所示,P(2,3)=1表明结点1的加入会缩短2到3的路径。本例4步依次如下:
  Floyd算法——任意两点间最短路径的动态规划算法 - 极夜.潜 - 极夜.潜的博客
  Floyd算法——任意两点间最短路径的动态规划算法 - 极夜.潜 - 极夜.潜的博客
  Floyd算法——任意两点间最短路径的动态规划算法 - 极夜.潜 - 极夜.潜的博客
  Floyd算法——任意两点间最短路径的动态规划算法 - 极夜.潜 - 极夜.潜的博客

矩阵D(4)中,无穷大元素表明其坐标对应的结点间无路径可达,其它元素表示两点间最短路径的长度。最终的P矩阵指示如何通过回溯得到两结点间的最短路径。例如:2到4的最短路径经过3,则有2-->3-->4;2到3经过1,则有2-->1-->3-->4;2到1再无结点(P中对应为0),则回溯结束,2到4之间的最短路径为2-->1-->3-->4,长度为D(2,4)=9。

  评论这张
 
阅读(4107)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018