最短路径算法--Dijkstra 算法,Bellmanford 算法,Floyd 算法,Johnson 算法.pdf
《最短路径算法--Dijkstra 算法,Bellmanford 算法,Floyd 算法,Johnson 算法.pdf》由会员分享,可在线阅读,更多相关《最短路径算法--Dijkstra 算法,Bellmanford 算法,Floyd 算法,Johnson 算法.pdf(38页珍藏版)》请在咨信网上搜索。
1、6.3.3 最短路径算法-Dijkstra 算法,Bellm anford 算法,Floyd 算法,Johnson 算法最短路径算法在交通地图上,两地点之间的路径通常标有长度,我们可以用加权有向来描述地图上的 交通网。加权有向图中每条路径都有一个路径权值,大小为该路径上所有边的权值之和。本 节将重点讨论顶点之间最短路径问题。在实际问题中,路径权值还可以表示其它类型的开销,例如两地之间行程所需要的时间;两任务切换所需代价等。本节讨论的最短路径具有方向性,问题用图的术语描述为:给定一个起始顶点S和一个 结束顶点t,在图中找出从S到t的一条最短路径。称S为路径源点,t为路径汇点。最短路径问题可以进一
2、步分为单源最短路径和全源最短路径。单源最短路径定义为,给定起始顶点S,找出从s到图中其它各顶点的最短路径。求解单源最短路径的算法主要是Dijkstra算法和Bellman-Ford算法,其中 Dijkstra算法主要解决所有边的权为非负的单源最短路径问题,而Bellman-Ford 算法可以适用于更一般的问题,图中边的权值可以为负。全源最短路径定义为,找出连接图中各对顶点的最短路径。求解全源最短路径的算 法主要有Floyd算法和Johonson算法,其中Floyd算法可以检测图中的负环并可 以解决不包括负环的图中的全源最短路径问题;Johonson算法同样也是解决不包 含负环的图的全源最短路径
3、问题,但是其算法效率更高。1基本原则最短路径算法具有最短路径的最优子结构性质,也就是两顶点之间的最短路径包括路径 上其它顶点的最短路径。具体描述为:对于给定的带权图G=(V,E),设p=vi,V2,V,是从V1到Vk的最短路径,那么对于任意i和j,lijk,Pij=d v+a(v,w)d w v+a(v,w);p w=v;2单源最短路径单源最短路径定义为,给定起始顶点S,找出从s到图中其它各顶点的最短路径。这里 我们将得到的结果称为最短路径树(shortest path tree),其中树根为起始顶点s。2.1 Di jkstra 算法在前面章节中讨论最小支撑树时,我们讨论了 Prim算法:每
4、次选择一条边添加到最小 支撑树MST中,这条边连接当前MST中某个顶点和尚未在MST中的某个顶点,其权值最小。采用类似的方案可以计算最短路径树SPT。开始时将源点添加到SPT中,然后,每次增加一 条边来构建SPT,所取的边总是可以给出从源点到尚未在SPT中某个定点的最短路径。这样,顶点按照到源点的距离由小到大逐个添加到SPT中。这种算法称为Dijkstra算法,具体的 实现跟Prim类型,分为普通实现和基于最小堆的实现。首先,我们需要明确Dijkstra算法的适用范围是权值非负的图,即解决带有非负权值 的图中的单源最短路径问题。下面对这一属性做简单分析。给定顶点S,通过Dijkstra算法得到
5、的最短路径树中,从根s到树中各顶点u的树路 径对应着图中从顶点s到顶点u的最短路径。归纳证明如下:假设当前所得到的子树具有这一属性,向当前子树中添加新的顶点u,满足:从顶点s 出发,经过当前SPT中的树路径,并最终到达u。可以通过选择,使得所选择的s到u的路 径比所有满足条件的路径都更短。所以增加一个新的顶点将增加到达该顶点的一条最短路 径。如果边的权值可以为负数,那么上述证明过程将不成立,上述证明中已经假设了向当前 子树中添加新的边时,路径的长度不会递减。然而在具有负权值的边的图中,这个假设不能 满足,因为所遇到的任何边都可能指向子树中的某个顶点,而且这条边可能有一个负权值,从而会使得到达该
6、顶点的路径比树路径更短。以下是Dijkstra算法的实现,Dijkstra算法和基于优先队列的Dijkstra算法都在 Single Source Shortest Pa ths类中实现,类中包括存放每个顶点到源点的最近距离D 数组和存放各个顶点的在SPT中的父节点V数组。电/*Dijkstra算法寻找图中单源点最短路径夫输入为待寻找的图G以及源点s夫param s 起始顶点*/public void Dijkstra(int s)if(s 0)return;int nv=G.get_nv();/初始化for(int i=0;i (Dv+G.getEdgeWt(w)/更新最短距离DG.edge
7、_v2(w)=Dv+G.getEdgeWt(w);/更新父节点VG.edge_v2(w)=v;System.out.printIn(rx(+w.get_vl()+,+w.get_v2()+G.getEdgeWt(w);)/根据V数组建立最短路径树SPTspt.addChild(s,s,new ElemItem(D0);spt.setRoot(s);int f=-1;/顶点标记数组,V_idxi=1表示i顶点已经在SPT中,否则不再SPT中int V_idx=new intV.length;/初始化for(int i=0;i V_idx.length;i+)V_idxi=0;/起始顶点s已经在S
8、PT中V_idxs=1;while(true)f=-1;for(int i=0;i=0&V_i dxVi-一 1&spt.addChild(Vi,i,new ElemItem(Di)V_idxi=1;f=1;)/一次都没有添加,结束循环if(f=-1)break;)电算法中每次从SPT之外的顶点中选择一个顶点v,对应边的权值最小;然后对这条边进 行松弛操作。算法迭代直至图中所有顶点都在SPT中为止。以图为例,求解图的最短路径树,起始顶点为顶点0。根据算法实现过程,提取图中最 短路径数的过程如图(a-c)。图Dijkstra算法示例图算法初始化阶段每个顶点到起始顶点S的最短路径长度为8。首先从起
9、始顶点0开始,寻找相邻顶点1和顶点5,并对其进行松弛操作。此时SPT中根节点为0,两个(未确定)子 节点为顶点1和顶点5。其中顶点0着色为灰色(赋值1,只有着色为灰色的顶点确定为SPT 中顶点。由于顶点1和顶点5对应的边可能会在以后的操作中进行松弛操作,所以SPT中这两个顶 点是未确定的,顶点着色也未改变。选择与当前SPT中顶点0最近的顶点5,首先将顶点5确定为SPT中顶点0的子节点;然 后对其相邻顶点进行松弛操作。相邻顶点为顶点1和顶点4,其中顶点4的最短距离需要更新。选择与当前SPT中顶点0、顶点5最近的顶点4,首先将顶点4确定为SPT中顶点5的子 节点;然后对其相邻顶点进行松弛操作。相邻
10、顶点为顶点2和顶点3,这两个顶点都需要更 新最短距离。接下来将先后选择边(5,1)、(4,2)和(4,3),并进行松弛操作。最终得到的SPT为:将图作为算法代码的测试输入,编写示例程序如下:电public class DijkstraExample public static void main(String args)GraphLnk GL=Utilities.BulidGraphLnkFromFile(Graph、graph8.txtn);SingleSourceShortestPaths sp=new SinglesourceShortestPaths(GL);sp.Dijkstra(0
11、);sp.spt.ford_print_tree();)算法跟踪顶点选择和边松弛操作的过程,每个顶点距离起始顶点的最短距离记录在数 组D中,顶点的父节点保存在数组V中,最终利用前面章节中讨论的广义树存放SPT。程序 运行结果为:relax(0,1),41 relax(0,5),29O found(0,5)f 2 9 relax(5,4),21O found(5 r 4),21 relax(4,2),32 relax(4,3),3 6O found(5,1),2 9O found(4,2),32O found(4,3),366节点,前序遍历打印:I-0.0(0)|-41.0(1)|-29.0(5
12、)|-50.0(4)I-82.0(2)|-8 6.0(3)结果第一部分为算法将各顶点添加到SPT中以及各条边的松弛操作。第二部分表示算法 最终获得的SPT树。读者可以自行对照并理解示例程序的运行结果和上面分析步骤。在前面章节中,Prim算法可以借助于优先队列(最小堆)来提高效率,这里也可以采 用这种策略。具体算法过程其读者自行理解,本书提供该算法的实现,具体参见程序。通过 分析可以发现基于最小堆的Dijkstra算法的时间开销与E/gV成正比。2.2 Bel ImanFord 算法Bellman-Ford算法诞生于20世纪50年代,对于不包含负环的图,该算法可以简单有效 地求解图的单源最短路径
13、问题。算法的基本思路非常简单:以任意顺序考虑图的边,沿着各 条边进行松弛操作,重复操作IV|次(|V|表示图中顶点的个数)o对有向带权图G=V,E,从顶点s起始,利用Bellman-Ford算法求解各顶点最短距 离,算法描述如下:for i=0;i|V|;i+for each edge u,v ERELAX u,v 算法对每条边做松弛操作,并且重复IVI次,所以算法可以在于|V|E|成正比的时间 内解决单源最短路径问题。算法I分简单,但是在实际中并不被采用,对其做简单的改进就 可以得到更高效算法。我们对算法的正确性做简单分析。设每个顶点距离起始顶点s的最短距离存放在数组D 中。我们首先假设以下
14、命题为真:算法在第i遍处理之后,对于所有顶点u,Du不大于s 到u且包含i条(或更少)边的最短路径的长度。根据以上命题,经过|V|-1次迭代后,对所给定的顶点u,Du为任何从s到u且包含 IV|-1条(或更少)边的最短路径的长度的下界。此时算法可以停止迭代,因为包含|V|条边(或更多)的任何路径将必然有一个环,通过去除这个环将可以找到一条包含|V|-1(或更 少)边的路径,该路径长度不大于去环前的路径的长度。所以Du同时又是从s到u的最 短路径的上界,既然Du同时是下界和上界,那么必然是最短路径的长度。下面我们对上述命题做归纳证明。i为0时,命题自然为成立;假设命题对于i成立,那么对于每个给定
15、的顶点u分两种情况:,在从s到u包含i+1条(或更少)边的路径中,如果其中最短路径长度为i(或更 少),那么Du不做调整。否则,有一条从S到U且包含i+1条边的路径,其长度比S到U且包含i(或更少)条边的任何路径都短。该路径必然由S先到达某个顶点W的路径再加上边 w,U)所组成。由归纳假设,Dw是从S到W的最短距离的上边界,而且第i+1遍处理会 对各条边进行检查。所以算法在第i+1遍处理之后,对于所有顶点U,Du不大于S到u且包含i条(或更 少)边的最短路径的长度然而算法每遍处理对于各条边都进行检查将是很大的浪费,因为有大量的边并不会导致 有效的松弛。事实上,唯一可能导致调整的边仅为某些特定顶
16、点出发的边:这些顶点的值在 上一遍处理中发生了变化。那么可以对算法进行优化,即每遍处理只对特定顶点出发的边做松弛操作。可以将发生 变化的顶点的记录下来,在下一遍处理时对一这些顶点为源点的边做松弛操作。我们使用队 列结构来存储这些顶点,以下是算法的实现,算法在MinusWeightGraph类中实现,类 中包括存放每个顶点到源点的最近距离D数组和存放各个顶点的在SPT中的父节点V数组。电/*Bellman-Ford算法求解给定图的单源最短路径;*图中边的权值可以是负数。*param s 起始顶点*/public void BellmanFord(int s)if(s 0)return;int n
17、v=G.get_nv();/初始化for(int i=0;i nv;i+)Di=Double.MAX_VALUE;Vi=-2;G.setMark(i,0);)/队歹UQLinkQueue Q=new LinkQueue();/起始顶点的距离为0D s =0;/将起点s和nv添加到队列中int M=Integer.MAX_VALUE;Q.enqueue(new Elemltem(s);Q.enqueue(new Elemltem(M);System.out.print();Q.printQueue();/迭代过程,直到Q为空while(Q.currSize()!=0)int f=-1;int v
18、,N=0;while(M=(v=(Integer)(Q.dequeue().elem).intValue()if(N+nv)f=1;break;Q.enqueue(new Elemltem(M);)System.out.print(n0);Q.printQueue();if(f=1)break;/对v的所有相连的边efor(Edge e=G.firstEdge(v);G.isEdge(e);e=G.nextEdge(e)/更新e的终点w的距离int w=e.get_v2();double P=Dv+G.getEdgeWt(e);/如果w经过v的路径更短,则更新w的距离if(P Dw)D w=P
19、;/将w添加到队列中Q.enqueue(new Elemltem(w);/将w的父节点重置为vV w=v;)System.out.print(n);Q.printQueue();)/根据V数组建立最短路径树SPTmst.addChild(s,s,new ElemItem(Ds);mst.setRoot(s);int f=-1;/顶点标记数组,V_idxi=1表示i顶点已经在SPT中,否则不再SPT中 int V_idx=new intV.length;/初始化for(int i=0;i V_idx.length;i+)V_idxi=0;/起始顶点s已经在SPT中V_idxs=1;while(t
20、rue)f=-1;for(int i=0;i=0&V_idxVi1&mst.addChild(Vir i,new ElemItem(Di)V_idxi=1;f=1;)/一次都没有添加,结束循环if(f=-1)break;)算法实现过程中,用无穷大数Integer.MAX_VALUE分离队列中两遍处理的顶点,变量N 记录操作了几遍,当N等于顶点个数时算法完成。算法最终广义树形式的SPT。以图为示例,起始顶点为顶点4,根据算法过程,SPT创建过程如图图中记录 每遍处理后各顶点的最短距离和队列中的顶点标号。图Bellman-Ford算法的示例图0 1 2 3 4 5D8 8 8 8 0 8a012
21、3 4 sD|8|8|32|36|0|8|bI。I 5 I 80 1 2 3 4 5|81|122|32|36|0|-2|最终得到的SPT为:图Bliman ford算法求解得至IJ的SPT 以图作为示例,编写算法示例程序:电Ipublic class BellmanFordExample public static void main(String args)GraphLnk GL=Utilities.BulidGraphLnkFromFile(Graph、graph10.txt);MinusWeightGraph MWG=new MinusWeightGraph(GL);MWG.Bellm
22、anFord(4);System.out.printin();MWG.mst.ford_print_tree();)程序运行结果为:队列的元素项从列首到列尾为:4,2147483647.O队列的元素项从列首到列尾为:2147483647.队列的元素项从列首到列尾为:2147483647,2,3.O队列的元素项从列首到列尾为:3,2147483647.队列的元素项从列首到列尾为:3,2147483647.O队列的元素项从列首到列尾为:2147483647.队列的元素项从列首到列尾为:2147483647,0,5.O队列的元素项从列首到列尾为:5,2147483647.队列的元素项从列首到列尾为:
23、5,2147483647,1.。队列的元素项从列首到列尾为:2147483647,1.队列的元素项从列首到列尾为:2147483647,1,1.。队列的元素项从列首到列尾为:1,2147483647.队列的元素项从列首到列尾为:1,2147483647,2.O队列的元素项从列首到列尾为:2147483647,2.队列的元素项从列首到列尾为:2147483647,2.O队列的元素项从列首到列尾为:2147483647.队列的元素项从列首到列尾为:2147483647.。队列为空6节点,前序遍历打印:|-0.0(4)|-36.0(3)|-2.0(5)I-31.0(1)I-20.0(2)I-81.0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最短路径算法-Dijkstra 算法 Bellmanford 算法 Floyd 算法 Johnson 算法 路径 Dijkstra Bellmanford Floyd Johnson
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【曲****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【曲****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
链接地址:https://www.zixin.com.cn/doc/4901598.html