ACM之图论.pptVIP

主要内容： 1.最短路算法及其应用 2.生成树问题 3.图论中的圈和块问题 4.简单网络流问题  1.最短路算法及其应用 最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。 乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？ 一个在生活中常见的例子是: 一种可能的方法是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。 然而我们很容易看到，即使不考虑含回路的路径，依然存在数以百万计的行车路线! 实际上，其中绝大多数路线我们是没必要考虑的。 这时候，我们应该用一种系统的方法来解决问题，而不是通常人们所用的凑的方法和凭经验的方法。 在最短路问题中，给出的是一有向加权图G=(V,E)，在其上定义的加权函数W:E→R为从边到实型权值的映射。路径P=(v0, v1,……, vk)的权是指其组成边的所有权值之和： 定义u到v间最短路径的权为： 从结点u到结点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的最短路径矛盾。（证毕） 常见的最短路问题 单目标最短路径问题： 找出从每一结点v到某指定结点u的一条最短路径。 把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。 单对结点间的最短路径问题：对于某给定结点u和v，找出从u到v的一条 最短路径。如果我们解决了源结点为u的单源问题，则这一问题也就获得 了解决。对于该问题的最坏情况，从渐进意义上看，目前还未发现比最好 的单源算法更快的方法。 每对结点间的最短路径问题：对于每对结点u和v，找出从u到v的最短路径。 我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。 最短路常用算法 一、Dijkstra算法 二、Bellman-Ford算法 三、SPFA算法 四、floyd算法（略） 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. S 3. Q ← V[G] 4. While Q 5. Do u ← EXTRACT-MIN(Q) 6. S ← S U {u} 7. For 每个顶点v Adj[u] 8. Do RELAX(u,v,w) Dijkstra算法 适用条件: 所有边的权值非负 定理2 每当结点u插入集合S时，有d[u]= (s,u)成立。 简证：我们每次选择在集合V-S中具有最小最短路径估计的结点u，因为我们约定所有的边权值非负，所以有可能对结点u进行松弛操作的结点必不在集合V-S中（否则与结点u的定义矛盾），因此只会在集合S中。又由于我们选取结点进入S时，S中的结点已全部进行过松弛操作了，所以d[u]的值不会再发生改变。因此d[u]= (s,u)。（证毕） 效率: ?用一维数组来实现优先队列Q，O( )，适用于中等规模的稠密图 ?二叉堆来实现优先队列Q，O((E+V)logV)，适用于稀疏图 ?用Fibonacci堆来实现优先队列Q的话，O(VlogV)，可惜编程复杂度过高，理论价值远大于实用价值 Bellman-Ford算法 Bellman-Ford