《中科院算法课程第6-2节-图算法-最短路》由会员分享，可在线阅读，更多相关《中科院算法课程第6-2节-图算法-最短路（20页珍藏版）》请在金锄头文库上搜索。
1、2019/5/24,1,电子与通信工程学院 ,第6.2节 最短路 Shortest path,1,6.2.1 问题的定义 6.2.2 Bellman-Ford 算法 6.2.3 每对顶点间的最短路问题,提纲,2019/5/24,2,例如：从中关村到玉泉路的最短路 定义：给出一个有向图G(V, E), 加权函数w:ER为边到实型权值的映射。路径p= 的权是指其边的所有权值之和： 定义从u到v间的最短路径的权为:,6.2.1问题的定义,2019/5/24,3,6.2.1问题的定义,2019/5/24,4,最短路径的最优子结构 最短路径算法的性质：一条两顶点间的最短路径包含路径上其他最短路径； 这种
2、最优子结构性质是动态规划或贪心算法是否适用的标记； 后面的Dijkstra算法是一个贪心算法 Folyd-Warshall算法是一个动态规划算法,6.2.1问题的定义,2019/5/24,5,最短路径的子路径是最短路径 引理1：给出一个有向图G(V, E), 加权函数w:ER。设路径p= 的权是v1到vk的最短路径。则对于1i j k, pij= 是i到j的最短路径。 证明：将路径p分解为v1 vi vj vk,则有： w(p) = w(p1i)+w(pij)+w(pjk). 假设存在一条路径pij= vi vj 其权值w(pij) w(p1i)+w(pij)+w(pjk). 这与p是最短路径
3、矛盾。,6.2.1问题的定义,2019/5/24,6,负权边与回路,3,5,-1,11,0,3,-4,4,5,2,6,-3,3,-6,8,7,s,a,b,c,d,e,f,g,6.2.1问题的定义,2019/5/24,7,最短路径的表示 引理1：对于有向图G(V, E), 定义前趋子图G(V , E ) 定义顶点集V 为具有非空前趋的顶点加上源点s V = 有向边集E 是由V 中的顶点导出的边集 E =,6.2.1问题的定义,2019/5/24,8,松弛技术 用(V)的时间来初始化前趋 INITIALIZE-SINGLE-SOURCE(G, s) For each vertex do dv v
4、NIL ds 0,6.2.1问题的定义,2019/5/24,9,松弛技术 用(V)的时间来Relex RELEX(u, v, w) if dv du +w(u, v) then dv du +w(u, v) v u,5,u,9,v,5,u,7,v,2,RELEX,2,5,u,6,v,5,u,6,v,2,RELEX,2,6.2.2 Bellman-Ford算法,2019/5/24,10,算法流程 BELLMAN-FORD(G, w, s) INITIALIZE-SINGLE(G, s) for i to VG do for each edge do RELEX (u, v, w) for eac
5、h edge do if dv du +w(u, v) then return FALSE Return TURE,6.2.2 Bellman-Ford算法,2019/5/24,11,算法过程,0,s,t,x,y,z,6,7,8,5,-2,7,9,2,-3,-4,6.2.2 Bellman-Ford算法,2019/5/24,12,定理：对于有向图G(V, E), 源点s , 权函数w:ER，对该图运行Bellman-Ford算法。若G不包含s的可达负权回路, 则算法返回TRUE, 对于所有顶点 ， 有 成立。其前趋子图G是以s为根的最短路径树。如果若G包含s的可达负权回路, 则算法返回FALS
6、E。 证明：见板书。,6.2.3每对顶点间的最短路问题,2019/5/24,13,输入：有向图G(V, E) 输出：每对顶点之间的最短路 定义 一个nxn的矩阵W(wij) 表示边的权值： 定义 表示顶点i到顶点j的最短路径权值，也是算法终止时的输出值,6.2.3每对顶点间的最短路问题,2019/5/24,14,此时，每个顶点i都有一个前趋子图， 其中 本章要讲述一个动态规划算法，用于计算任意两顶点间的最短路，每次循环都是一个与矩阵乘法像类似的操作，因此我们用矩阵乘法作类比,6.2.3每对顶点间的最短路问题,2019/5/24,15,定义： 是顶点i到j 之间至多包含m条边的最短路的权值最小值
7、。 递归定义： 假设顶点i到j 之间至多包含n-1条边，则多于n条边的最短路径权值等同： EXTENT-SHORTEST-PATH给定矩阵L(m-1)包含了最多为m-1条边的最短路径，和W, 返回矩阵L(m)，就是把已经计算出来的的最短路路径延长一条边,6.2.3每对顶点间的最短路问题,2019/5/24,16,自底向上计算最短路： EXTEND-SHORTEST-PATH(L, W) nrowsL Let L=lij be an nxn matrix for i 1 to n do for j to n do for lij for k 1 to n do lijmin(lij, lik+w
8、kj) return L,计算AB矩阵乘法： MATRIX-MULTIPLY(A, B) nrowsA Let C=lij be an nxn matrix for i 1 to n do for j to n do for cij 0 for k 1 to n do cijcij +aikbkj) return C,6.2.3每对顶点间的最短路问题,2019/5/24,17,运行时间 L(1)=L(0)W=W L(2)=L(1)W=W(2) L(3)=L(2)W=W(3) L(n-1)=L(n-2)W=W (n-1) 改进后的运行时间 L(1)=L(0)W=W L(2)=W2=WW L(4)
9、=W4=W2W2,ALL-PAIRS-SHORTEST-PATHS(W) nrowsL Let L(1) W m 1 While mn-1 do L(2m) EXTEND-SHORTEST_PATH(L(m), ,L (m) ) m 2m Return L(m),6.2.3每对顶点间的最短路问题,2019/5/24,18,Floyd-Warshall算法 主要是基于以下观察：设G的顶点为V=1, 2,n, 对某个k考虑顶点的一个子集1, 2,k。 对任意的一对顶点 ，考察从i到j且中间顶点皆属于集合 1, 2,k的所有子路径，假设p是其中最短的路径，则有如下关系成立： 1）如果k不是路径p的中
10、间顶点，则p的所有中间顶点都在集合1, 2,k-1中。 2）如果k是路径p的中间顶点，则可以将p分解为 。其中p1是从i到k的一条最短路径，其所有顶点属于集合1,2,.,k-1，p2是从k到j的一条最短路径，其所有顶点属于集合1,2,.,k-1。 由此可以导出解决每对顶点之间最短路径的递归解，设 是从i到j，满足顶点集合都在子集1, 2,k中的最短路径。则可以给出如下递归式：,6.2.3每对顶点间的最短路问题,2019/5/24,19,Floyd-Warshall算法 nrowsW D(0) W for k 1 to n do for j 1to n do for i 1to n do return D(n),谢 谢,2019/5/24,20,
