《图的基本算法.ppt

执行过程 Company Logo Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 执行过程 Company Logo Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 最短路概述 最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题 乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？ 在乘车旅行的例子中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。 Company Logo Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 最短路概述 我们一般所将的都是单源最短路径问题，即我们希望找出从某给定点s到每个顶点的最短路径。 不过有许多其他的问题也可以用最短路算法解决 单目标最短路径问题： 找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。 单对结点间的最短路径问题：对于某给定结点u和v，找出从u到v的一条最短路径。如果我们解决了源结点为u的单源问题，则这一问题也就获得了解决 每对结点间的最短路径问题：对于每对结点u和v，找出从u到v的最短路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。 Company Logo Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 最短路涉及到的问题 负权边值：在某些最短路的实例中，可能存在权值为负的边。如果存在一条从s可达的负权回路，那么最短路的权的定义就不能存在了。 因为只要穿越负权回路任意次我们就可以发现从s到e可以无限变小。 Company Logo Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 最短路涉及到的问题 回路：一条最短路径能包含回路吗？它不能包含负权回路。它也不会包含正权回路，因为从路径上移去回路后回路后可以产生一个具有相同源点和终点，权值更小的路径。 Company Logo Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 松弛技术 对于每个顶点v,都设置了一个属性d[v],用来描述从源点s到v的最短路的上界，称为最短路径估计。 init() { for(int i=0;in;i++) d[i]=∞; d[s]=0 } Relax(u,v,w) { If(d[v]d[u]+w) d[v]=d[u]+w; pre[v]=u; } 三角不等式：对于任意边(u,v)，有δ(s, v) ≤ δ(s, u) + w(u, v). Company Logo Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. Company Logo 最短路算法 Dijkstra SPFA Bellman Ford 最短路算法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 最短路算法 我们着重讨论两种常用算法：Dijkstra算法和Bellman-Fo