Lecture6-最短路径算法.ppt

1 最短路径算法 高文宇gwyy 2 最短路径问题 给定的带权图中 从节点u到v的最短路径即所有路径中边的权值之和最小的路径 有如下几种变形 1 单源最短路径 2 单终点最短路径 3 单对顶点最短路径 4 每对顶点间的最短路径 3 最短路径的结构 最短路径问题的最优子结构 Lemma24 1 Subpathsofshortestpathsareshortestpaths 给定一个带权有向图G V E 和权值函数w E R 设p v1 v2 vk 从v1到vk的最短路径 对于任意i和j 其中1 i j k 设pij 是路径p从vi到vj的子路径 则pij是一条从vi到vj的最短路径 4 负权值边 Negative weightedges若图G V E 不包含从源点s可达的负权回路 则对所有v V 则最短路径的权的定义 s v 依然真确 即使允许有负权值边的存在 若包含有负权回路 则不存在 最短路径 某些算法如Dijkstra算法不允许有负边 某些算法如Bellman Ford算法则允许有负边 5 最短路径的表示 给定图G V E 我们对每一个节点v V设置其前驱节点 v 为另一节点或NIL 则借助于每个节点的前驱节点可以使用过程PRINT PATH G s v fromSection22 2来构造每一条最短路径 Print Path输出图G中从s到v的路径上的所有节点 PRINT PATH G s v 1ifv s2thenprints3elseif v NIL4thenprint nopathfrom s to v exists 5elsePRINT PATH G s v 6printv 6 松弛技术 Relaxation 对每个顶点v V 都设置一个属性d v 用来描述从源点s到v 的最短路径权值的上界 称为最短路径估计 以下是对d v 和 v 的初始化过程 松弛一条边的 u v 的过程中要测试是否可以通过u 对迄今找到的到v的最短路径进行改进 若可以 则更新d v 和 v 以上伪代码实现对边 u v 的松弛 RELAX u v w 1ifd v d u w u v 2thend v d u w u v 3 v u INITIALIZE SINGLE SOURCE G s 1foreachvertexv V G 2dod v 3 v NIL4d s 0 7 Relax Relax INITIALIZE SINGLE SOURCE G s 1foreachvertexv V G 2dod v 3 v NIL4d s 0 RELAX u v w 1ifd v d u w u v 2thend v d u w u v 3 v u 8 松弛与最短路径算法 本章的每个算法都要调用INITIALIZE SINGLE SOURCE 然后重复对边进行松弛操作 另外 松弛是改变最短路径和前驱的唯一方式 本章中算法之间的区别在于对每条边进行松弛操作的次数 以及对边执行松弛操作的次序有所不同 在Dijkstra算法以及对DAG图的最短路径算法中 对每条边仅执行一次松弛操作 而在Bellman Ford算法中 对每条边要执行多次松弛操作 9 Bellman Ford 该算法运用松弛技术 对每个顶点v V 逐步减小从源s到v的最短路径的权的估计值d v 直至达到实际最短路径的权 s v 算法返回TRUE 当且仅当图中不含从源点可达的负权回路 BELLMAN FORD G w s 1INITIALIZE SINGLE SOURCE G s 2fori 1to V G 13doforeachedge u v E G 4doRELAX u v w 5foreachedge u v E G 6doifd v d u w u v 7thenreturnFALSE8returnTRUE该算法的运行时间为O VE 10 Bellman Ford示例 源点为s 距离d标记在节点内阴影边指示前驱值 每一趟按如下顺序进行松弛 t x t y t z x t y x y z z x z s s t s y b e 展示了每一趟的操作结果 11 Bellman Ford算法的正确性 引理24 2 设G V E 为带权有向图 源点为s 权函数为w E R 并假定G从s可达的负权值回路 则经过 V 1次BELLMAN FORD算法 2 4行 的迭代 对任何s可达的节点v有 d v s v ProofWeprovethelemmabyappealingtothepath relaxationproperty Consideranyvertexvthatisreachablefroms andletp v0 v1 vk wherev0 sandvk v beanyacyclicshortestpathfromstov Pathphasatmost V 1edges andsok V 1 Eachofthe V 1iterationsoftheforloopoflines2 4relaxesallEedges Amongtheedgesrelaxedintheithiteration fori 1 2 k is vi 1 vi Bythepath relaxationproperty therefore d v d vk s vk s v 12 Bellman Ford算法的正确性 Theorem24 4 CorrectnessoftheBellman Fordalgorithm LetBELLMAN FORDberunonaweighted directedgraphG V E withsourcesandweightfunctionw E R IfGcontainsnonegative weightcyclesthatarereachablefroms thenthealgorithmreturnsTRUE wehaved v s v forallverticesv V andthepredecessorsubgraphG isashortest pathstreerootedats IfGdoescontainanegative weightcyclereachablefroms thenthealgorithmreturnsFALSE 如上图所示 当执行完Bellman Ford算法时 按su uw wu uv的顺序进行松弛 有 d v d u w u v 13 DAG中的最短路径 按顶点的拓扑序列对加权DAG图的边进行松弛后 可以在 V E 时间内计算出单源最短路径 DAG SHORTEST PATHS G w s 1topologicallysorttheverticesofG2INITIALIZE SINGLE SOURCE G s 3foreachvertexu takenintopologicallysortedorder4doforeachvertexv Adj u 5doRELAX u v w 14 Dijkstra算法 Dijkstra算法中设置了一个顶点集S 从源点s出发到集合中的顶点的最短路径的权值均已确定 算法反复选择具有最短路径估计的顶点u V S 并将u加入S 对u的所有出边进行松弛 算法中使用了最小优先队列Q 排序关键字为d值 15 Dijkstra算法 要求所有边的权值非负 DIJKSTRA G w s 1INITIALIZE SINGLE SOURCE G s 2S 3Q V G 4whileQ 5dou EXTRACT MIN Q 6S S u 7foreachvertexv Adj u 8doRELAX u v w 16 Dijkstra算法 Dijkstra算法 17 问题 1 给出一个含负权边的图的实例 说明Dijkstra算法对其运行时是错误的 2 为了求图中的最长路径 设想将图中所有的边的权值都取负值 能用最短路径算法求出最长路径吗 18 问题解答 1 最短的最短路径不再成立 因为通过负权边后 某条最短路径可能较之前产生的最短路径更短 19 每对顶点间的最短路径 若运行有负权值的边 则不能采用Dijkstra算法 必须对每个顶点运行一次Bellman Ford算法 因此总的运行时间为O V2E 为了求解图的输入邻接矩阵的每对顶点间的最短路径问题 不仅要算出最短路径的权值 还需计算出一个前驱矩阵 以便获得最短路径途经的节点 20 最短路径的结构 设是从顶点i到顶点j的至多包含m条边的任何路径的权值最小值 当m 0时 从i到j存在一条不包含边的最短路径当且仅当i j 因此有 21 最短路径的递归解 如下 式中后者是通过计算j的所有可能前驱k而得到的 22 自底向上计算最短路径权值 把矩阵W wij 作为输入 计算一组矩阵L 1 L 2 L n 1 其中对m 1 2 n 1 有L 1 lij m 最后一个矩阵L n 1 包含了最短路径权值 Observethatforallverticesi j V andsoL 1 W 23 EXTEND SHORTEST PATHS EXTEND SHORTEST PATHS 给定矩阵L m 1 和W 返回矩阵L m 24 SLOW ALL PAIRS SHORTEST PATHS SLOW ALL PAIRS SHORTEST PATHS W SLOW ALL PAIRS SHORTEST PATHS W 1n rows W 2L 1 W3form 2ton 14doL m EXTEND SHORTEST PATHS L m 1 W 5returnL n 1 25 示例 示例 26 EXTEND SHORTEST PATHS与矩阵乘法的相似性 利用对矩阵乘法的理解对算法进行加速 Wn Wn 2 Wn 2 可将运行时间从O V4 改进到O V3lgV 27 Floyd Warshall算法 Floyd Warshallalgorithm runsinO V3 28 最短路径的结构 Floyd Warshall算法考虑最短路径上的中间节点 intermediate 简单路径p v1 v2 vl 上的中间节点是除v1和vl 以外的任意节点 29 解的结构 设G的节点为V 1 2 n 对参数k考虑节点集 1 2 k 对任意一对节点i j V 考虑从i到j且中间节点都属于集合 1 2 k 的所有路径 设p是其中的最短路径 记为d i j k 有如下结论 若k不是路径p的中间节点 则p的所有中间节点属于集合 1 2 k 1 即d i j k d i j k 1 若k是p的中间节点 则如图Figure25 3 ByLemma24 1 可将p 分解为两条子路径 即i k j p1是从i到k中间节点属于集合 1 2 k 1 的最短路径 p2是从k到j中间节点属于 1 2 k 1 的最短路径 30 递归解 Floyd Warshall算法的递归解 d i j k 表示从i到j且中间节点都属于集合 1 2 k 的所有路径中的最短路径的权值 31 Floyd Warshall算法 Floyd Warshall算法 FLOYD WARSHALL W 1n rows W 2D 0 W3fork 1ton4dofori 1ton5doforj 1ton6