计算机问题求解一论题3-9 - All-Pair Shortest Paths 2018年11月6日
计算机问题求解 – 论题3-9 - All-Pair Shortest Paths 2018年11月6日
算法的输入形式 2 3 4 0 3 8 00 3 8 0 0∞ 1 > 4 0 5 2 -5 0 5 4 00 00 00 6 0 6
算法的输入形式
前驱节点矩阵 PRINT-ALL-PAIRS-SHORTEST-PATH(Π,i,j) 0???? 1 ifi==j ?0??? 2 print i ■π: ??0?? 3 elseif ij =NIL 4 ?5403 print“no path from”i“to”j"exists 5 else PRINT-ALL-PAIRS-SHORTEST-PATH(TI,i.ij) ????0 6 print j ■π42=5是什么意思? ■节点4到节点2的最短路径是什么? 口 递归调用的顺序是(π,4,2),(π,4,5),(π,4,3),(,4,4) 03 输出的顺序是:4,3,5,2
前驱节点矩阵 ◼ 𝜋: 0? ? ? ? ? 0? ? ? ? ? 0? ? ? 5403 ? ? ? ? 0 ◼ 𝜋4 , 2=5是什么意思? ◼ 节点4到节点2的最短路径是什么? ❑ 递归调用的顺序是(𝜋,4,2), (𝜋,4,5), (𝜋,4,3), (𝜋,4,4) ❑ 输出的顺序是:4,3,5,2
最优子结构:对于任意i,j间最短路p,其间的 任意路径均最短 假设这是从到的最短通路,经过k If verticesiandare distinct,then we decompose path pinto k.where path p'now contains at most m-1 edges.By Lemma 24.1. p'is a shortest path fromitokand s)j 这对我们未来的“递归”有什么启发?
i k j 假设这是从i到j的最短通路,经过k p ’ 最优子结构:对于任意i,j间最短路p,其间的 任意路径均最短 这对我们未来的“递归”有什么启发?
一种“最优解”的递归定义方式 Now,letbe the minimum weight of any path from vertexito vertexjthat contains at most m edges. When m =0,there is a shortest path from i to j with no edges if and only if i=j.Thus, ifi=j, oifi卡j
一种“最优解”的递归定义方式
问题1: 在有10个点的图中,唔的直观含义是什么? 如果=7,能认定节点间的最短路径长度 是7吗?
一种“最优解”的递归定义方式 怎么从路-1去计算珊 Form1,we compute as the minimum of(the weight of a shortest path from i to j consisting of at most m-l edges)and the minimum weight of any path from i to j consisting of at most m edges,obtained by looking at all possible predecessors k ofj.Thus,we recursively define m)=min(-1).min 1<k< min (25.2) 1≤k≤n {-D+w}. The latter equality follows since wjj=0 for all j
一种“最优解”的递归定义方式 怎么从𝑙 𝑖𝑗 𝑚−1去计算𝑙 𝑖𝑗 𝑚
间题2: 如果定义矩阵L=(珊),L1,L2, …,L观-1分别表示什么含义?
间题3: 我们需要计算瑞吗? 为什么(,》=瑞1?
自底向上计算 The heart of the algorithm is the following procedure,which,given matrices L(m-1and W.returns the matrix L(m).That is,it extends the shortest paths com- puted so far by one more edge. EXTEND-SHORTEST-PATHS(L.W) 1 n =L.rows 2 let L'=()be a new n x n matrix 间题4: 3 for i Iton 4 forj 1to n 567 号=∞ one more for k Ito n 号=min(吗,lk+0对) edge”体现在 8 return L' 哪里?
自底向上计算 O(n3 )