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

极夜.潜的博客

 
 
 

日志

 
 

Dijkstra算法——单源最短路径的贪心算法  

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

  下载LOFTER 我的照片书  |

在图G中,给定s和t两个顶点。从s到t可以有多条路径,从这多条路中找出长度最小的路,这样的路称为从s到t的最短路径。单源最短路径是指只寻找某个特定的起点到终点的最短路径。Dijkstra算法的基本思想:在最短路径集合之外的所有顶点中,寻找通过最短路径集到达起始点s路径最短的顶点,加入最短路径集合,直至将终点t加入最短路径集。最短路径集是一颗以s为根的树,开始时,该集合仅包含起点s。因为在每次加入的顶点到起点s的路径总是最短,Dijkstra算法是一种贪心算法。

一、Dijkstra最短路径算法

设每条弧的长度均为非负值。已知图中最接近于起始顶点s的m个顶点以及从s到这些顶点的最短路径(从s到其本身的最短路径是0),s和这m个顶点已着色,寻找最接近于s的第m+1个顶点。对于已着色的m个顶点x,未着色的顶点记为y,把弧(x, y)接在从s到x的最短路后面,这样就得到从s经x到y的不同路径,这些路径中最短的就是从s到某个顶点y的最短路径,相应的y就是最接近于s的第m+1个顶点。因为所有弧的长度都是非负值,所以从s到最接近于s的第m+1个顶点的最短路必然只使用已着色的顶点作为中间顶点。从m=0开始,将这个过程重复进行下去,直至求得从s到t的最短路为止。具体步骤如下:

第1步 开始时所有弧和顶点都未着色。对每个顶点x指定一个数d(x),d(x)表示从s到x的最短路的长度(中间顶点均已着色)。开始时,令d(s)=0,d(x)=∞(对所有x≠s)。y表示已着色的最后一个顶点(刚着色的顶点)。对起始点s着色,令y=s。

第2步 对于每个未着色顶点x,重新定义d(x)=min{d(x),d(y)+a(y,x)}。
对于所有未着色顶点x,如d(x)=∞,则算法终止。因为此时从s到任一未着色的顶点都没有路。否则,对具有d(x)最小值的未着色顶点x进行着色。同时把弧(y,x)着色(指向顶点x的弧只有一条被着色)。令y=x。

第3步 如果t未着色,转第2步;如果t已着色,则算法终止,这时找到一条从s到t的最短路径。

二、应用实例:用Dijkstra算法找出如下有向图中从s到t的最短路径

  Dijkstra算法——单源最短路径的贪心算法 - 极夜.潜 - 极夜.潜的博客

第1步,开始时只有s着色,d(s)=0。而且对于所有x≠s,d(x)=∞。

第2步,y=s(s刚着色)。
d(a)=min{d(a), d(s)+a(s,a)}=min{∞,0+4}=4
d(b)=min{d(b), d(s)+a(s,b)}=min{∞,0+7}=7
d(c)=min{d(c), d(s)+a(s,c)}=min{∞,0+3}=3
d(d)=min{d(d), d(s)+a(s,d)}=min{∞,0+∞}=∞
d(t)=min{d(t), d(s)+a(s,t)}=min{∞,0+∞}=∞
由于d(c)=3是最小值,所以对c点着色,并对确定d(c)的弧(s,c)着色。

第3步,顶点t未着色,返回第2步,y=c(c刚着色)。
d(a)=min{d(a), d(c)+a(c,a)}=min{4,3+∞}=4
d(b)=min{d(b), d(c)+a(c,b)}=min{7,3+∞}=7
d(d)=min{d(d), d(c)+a(c,d)}=min{∞,3+3}=6
d(t)=min{d(t), d(c)+a(c,t)}=min{∞,3+∞}=∞
由于d(a)=4是最小值,所以对顶点a着色,并对确定d(a)的弧(s,a)着色。

第3步,顶点t未着色,返回第2步,y=a(a刚着色)。
d(b)=min{d(b), d(a)+a(a,b)}=min{7,4+3}=7
d(d)=min{d(d), d(a)+a(a,d)}=min{6,4+2}=6
d(t)=min{d(t), d(a)+a(a,t)}=min{∞,4+∞}=∞
d(d)=6是最小值,对d着色,确定d(d)的弧有两条(即(c,d)和(a,d)),可任选其中的一条,对其着色。

第3步,顶点t未着色,返回第2步,y=d(d刚着色)。
d(b)=min{d(b), d(d)+a(d,b)}=min{7,6+∞}=7
d(t)=min{d(t), d(d)+a(d,t)}=min{∞,6+2}=8
d(b)=7是最小值,对点b着色,对确定d(b)的弧(s,b)着色。

第3步,顶点t未着色,返回第2步,y=b(b刚着色)。
d(t)=min{d(t), d(b)+a(b,t)}=min{8,7+2}=8
对点t及弧(d,t)着色。最终的最短路树形图由弧(s,c)(s,a)(c,d)(s,b)和(d,t)组成,从s到t的最短路由弧(s,c)(c,d)和(d,t)组成,其长度为3+3+2=8。

三、算法解释

(1)所有顶点分为已着色和未着色顶点集两部分,程序中通常用CLOSE和OPEN表示。
(2)算法开始时,已着色顶点集为空,未着色顶点集为全部顶点,通过贪心策略对未着色顶点逐个着色(将未着色顶点集中的元素移到已着色顶点集);算法结束时,情况相反(如果要找某顶点到每个顶点的最短路径)。
(3)着色某顶点表示找到该顶点到起始顶点的最短路径。
(4)顶点着色的贪心策略:以已着色顶点为跳板,到起始顶点最近的未着色顶点将被着色。
(5)顶点着色的具体方法:(a)考察刚刚着色顶点相邻的所有未着色顶点,计算这些顶点通过该着色顶点到起始顶点的路径长。(b)由于每个顶点着色后均要执行此操作,因此和已着色顶点集相领的所有未着色顶点到起始顶点的路径长均已知。(c)对这些顶点(刚着色顶点相邻的顶点和以前已着色顶点相邻的顶点)中到起始顶点路径最短的顶点着色。
(6)同时对连接着色顶点的边着色,可以看成是根在起始顶点的树的生长过程,一旦到达目标顶点,生长过程就停止,树的每个结点到根的唯一路径即为这两点间的最短路径。即使求出到每个顶点的最短路径,该生成树也不一定是最小生成树。
(7)Dijkstra算法不适用含负权值的图。设想从图中找到一个环路,且这个环路中所有边的权值之和为负。那么通过这个环路,环路中任意两点的最短路径就可以无穷小下去。

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

历史上的今天

评论

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

页脚

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