算法合集之《最短路算法及其应用技术》

算法合集之《最短路算法及其应用技术》

ID:35069172

大小:316.50 KB

页数:23页

时间:2019-03-17

算法合集之《最短路算法及其应用技术》_第1页
算法合集之《最短路算法及其应用技术》_第2页
算法合集之《最短路算法及其应用技术》_第3页
算法合集之《最短路算法及其应用技术》_第4页
算法合集之《最短路算法及其应用技术》_第5页
资源描述:

《算法合集之《最短路算法及其应用技术》》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、最短路算法及其应用广东北江中学余远铭【摘要】最短路问题是图论中的核心问题之一,它是许多更深层算法的基础。同时,该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系,却也可以归结为最短路问题。本文较详尽地介绍了相关的基本概念、常用算法及其适用范围,并对其应用做出了举例说明,侧重于模型的建立、思考和证明的过程,最后作出总结。【关键字】最短路【目录】一、基本概念21.1定义21.2简单变体21.3负权边31.4重要性质及松弛技术4二、常用算法52.1Dijkstra算法52.2Bellman-Ford

2、算法72.3SPFA算法8三、应用举例103.1例题1——货币兑换103.2例题2——双调路径113.3例题3——Layout133.4例题4——网络提速1523/23四、总结18【正文】一、基本概念1.1定义乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离,如何找出这一最短行程?一种可能的方法是枚举出所有路径,并计算出每条路径的长度,然后选择最短的一条。然而我们很容易看到,即使不考虑含回路的路径,依然存在数以百万计的行车路线,而其中绝大多数是没必要考虑的。下面我们

3、将阐明如何有效地解决这类问题。在最短路问题中,给出的是一有向加权图G=(V,E),在其上定义的加权函数W:ER为从边到实型权值的映射。路径P=(v0,v1,……,vk)的权是指其组成边的所有权值之和:定义u到v间最短路径的权为从结点u到结点v的最短路径定义为权的任何路径。在乘车旅行的例子中,我们可以把公路地图模型化为一个图:结点表示路口,边表示连接两个路口的公路,边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。边的权常被解释为一种度量方法,而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失

4、或任何其他沿路径线性积累的数量形式。1.2简单变体单目标最短路径问题:找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向,我们就可以把这一问题转化为单源最短路径问题。单对结点间的最短路径问题:对于某给定结点u和v,找出从u到v的一条最短路径。如果我们解决了源结点为u的单源问题,则这一问题也就获得了解决。对于该问题的最坏情况,从渐进意义上看,目前还未发现比最好的单源算法更快的方法。每对结点间的最短路径问题:对于每对结点u和v,找出从u到v23/23的最短路径。我们可以用单源算法对每个结点作为源点运行一次就

5、可以解决问题。1.3负权边在某些单源最短路问题中,可能存在权为负的边。如果图G(V,E)不包含由源s可达的负权回路,则对所有,最短路径的权的定义依然正确。即使它是一个负值也是如此。但如果存在一从s可达的负权回路,最短路径的定义就不能成立了。从s到该回路上的结点不存在最短路径——因为我们总可以顺着找出的“最短”路径再穿过负权回路从而获得一权值更小的路径,因此如果从s到v的某路径中存在一负权回路,我们定义。图1含有负权和负权回路的图图1说明负的权值对最短路径的权的影响。每个结点内的数字是从源点s到该结点的最短路径的权。因

6、为从s到a只存在一条路径(路径),所以:。类似地,从s到b也只有一条通路,所以:。从s到c则存在无数条路径:,,等等。因为回路的权为6+(-3)=3>0,所以从s到c的最短路径为,其权为:。类似地,从s到d的最短路径为,其权为:。同样,从s到e存在无数条路径:,,等等.由于回路的权为3+(-6)=-3<0,所以从s到e没有最短路径。只要穿越负权回

7、路任意次,我们就可以发现从s到e的路径可以有任意小的负权值,所以:类似地,23/23因为g是从f可达的结点,我们从s到g的路径可以有任意小的负权值,则:。结点h,j,i也形成一权值为负的回路,但因为它们从s不可达,因此。一些最短路径的算法,例如Dijkstra算法,都假定输入图中所有边的权取非负数,如公路地图实例。另外一些最短路算法,如Bellman-Ford算法,允许输入图中存在权为负的边,只要不存在从源点可达的权为负的回路,这些算法都能给出正确的解答。特定地说,如果存在这样一个权为负的回路,这些算法可以检测出这种

8、回路的存在。1.4重要性质及松弛技术本文的算法所运用的主要技术是松弛技术,它反复减小每个结点的实际最短路径的权的上限,直到该上限等于最短路径的权。让我们看看如何运用松弛技术并正式证明它的一些特性。定理1(最优子结构)给定有向加权图G=(V,E),设P=为从结点v1到结点vk的一条最短路径,对任意i,j有i<=j<=k,设

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。