下载此文档

最短路算法及其应用.ppt


文档分类:通信/电子 | 页数:约30页 举报非法文档有奖
1/30
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/30 下载此文档
文档列表 文档介绍
最短路算法及其应用广东北江中学余远铭yyming@最短路问题是图论中的核心问题之一,它是许多更深层算法的基础。同时,该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系,却也可以归结为最短路问题。乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离,如何找出这一最短行程?一个在生活中常见的例子是:一种可能的方法是枚举出所有路径,并计算出每条路径的长度,然后选择最短的一条。然而我们很容易看到,即使不考虑含回路的路径,依然存在数以百万计的行车路线!实际上,其中绝大多数路线我们是没必要考虑的。这时候,我们应该用一种系统的方法来解决问题,而不是通常人们所用的凑的方法和凭经验的方法。定义在最短路问题中,给出的是一有向加权图G=(V,E),在其上定义的加权函数W:E→R为从边到实型权值的映射。路径P=(v0, v1,……, vk)的权是指其组成边的所有权值之和:1 1( ) ( , )ki iiw p w v v 定义u到v间最短路径的权为: min ( ):)w p u v u vv 如果存在由到的通路如果不存在从结点u到结点v的最短路径定义为权的任何路径。( ) )w p v 在乘车旅行的例子中,我们可以把公路地图模型化为一个图:结点表示路口,边表示连接两个路口的公路,边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。边的权常被解释为一种度量方法,而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。重要性质定理1 (最优子结构) 给定有向加权图G=(V,E),设P=<v1, v2,…, vk>为从结点v1到结点vk的一条最短路径,对任意i,j有i<=j<=k,设Pij=< vi, vi+1,…, vj>为从vi到vj的P的子路径,则Pij是从vi到vj的一条最短路径。证明:我们把路径P分解为<v1,v2,…,vi,vi+1,…vj,…vk>。则w(P)=w(P1i)+w(Pij)+w(Pjk)。现在假设从vi到vj存在一路径P’ij,且w(P’ij)<w(Pij),则将P中的路径Pij=(vi,vi+1,…vj)替换成P’ij,依然是从v1到vk的一条路径,且其权值 w(P1i)+w(P’ij)+w(Pjk)小于w(P),这与前提P是从v1到vk的最短路径矛盾。(证毕) 给定有向加权图G=(V,E),源点为s,则对于所有边(u,v) E,有:( , ) ( , ) ( , )s v s u wu v 证明: 从源点s到结点v的最短路径P的权不大于从s到v的其它路径的权。特别地,路径P的权也不大于某特定路径的权,该特定路径为从s到u的最短路径加上边(u,v)。(证毕)松弛技术INITIALIZE-SINGLE-SOURCE(G,s)1. For 每个结点 v V[G]2. Do d[v] ←3. [v] ← NIL4. d[s] 0对每个结点v V,我们设置一属性d[v]来描述从源s到v的最短路径的权的上界,称之为最短路径估计。我们通过下面的过程对最短路径估计和先辈初始化。RELAX(u,v,w)1. If d[v] > d[u] + w(u,v)2. Then d[v] ← d[u] + w(u,v)3. [v] ← u一次松弛操作可以减小最短路径的估计值d[v]并更新v的先辈域[v]常用算法一、Dijkstra算法二、Bellman-Ford算法三、SPFA算法Dijkstra算法Dijkstra算法中设置了一结点集合S,从源结点s到集合S中结点的最终最短路径的权均已确定,即对所有结点v S,有d[v]= (s,v)。算法反复挑选出其最短路径估计为最小的结点u V-S,把u插入集合S中,并对离开u的所有边进行松弛。Dijkstra(G,w,s)1. INITIALIZE-SINGLE-SOURCE(G,S)2. S3. Q ← V[G]4. While Q5. Do u ← EXTRACT-MIN(Q)6. S ← S U {u}7. For 每个顶点v Adj[u]8. Do RELAX(u,v,w)

最短路算法及其应用 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数30
  • 收藏数0 收藏
  • 顶次数0
  • 上传人hqpkhvg379
  • 文件大小0 KB
  • 时间2015-11-03