南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）多源最短路径算法

计算机问题求解一论题3-9 All-Pair Shortest Paths 2022年11月9 日

计算机问题求解 – 论题3-9 - All-Pair Shortest Paths 2022年11月9 日

算法的输入形式 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

算法的输入形式

最直观的解法 Bellman-Ford算法执行VI次 ■Dijkstra算法执行VI次 口f可能

最直观的解法 ◼ Bellman-Ford算法执行|V|次 ◼ Dijkstra算法执行|V|次 ❑ if可能

最优子结构：对于任意i,j间最短路p,其间的 任意子路径均最短 假设这是从到的最短通路，经过k If vertices i and j are distinct,then we decompose path p into ikj,where path p'now contains at most m-1 edges.By Lemma 24.1, p'is a shortest path from i to k,and sd(i.)=8(i,k+wki 这对我们未来的“递归”有什么启发？

i k j 假设这是从i到j的最短通路，经过k p ’ 最优子结构：对于任意i，j间最短路p,其间的 任意子路径均最短 这对我们未来的“递归”有什么启发？

一种“最优解”的递归定义方式 ■表达节点到的最短路径长度的动态规划递归表达式： 口1，L(i,j)=w 2.L(i,j)=min {L(i,k)+Wkj 1≤k≤n 但参考书上采用了另外一种递归表达方式，有何不同？ Now,letbe the minimum weight of any path from vertex ito vertexthat 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. fi≠j. =mm(g-”经-”+)

一种“最优解”的递归定义方式 ◼ 表达节点i到j的最短路径长度的动态规划递归表达式： ❑ 1，𝐿(𝑖,𝑗) = 𝑤𝑖𝑗 ❑ 2, 𝐿 𝑖,𝑗 = min 1≤𝑘≤𝑛 {𝐿(𝑖, 𝑘) + 𝑤𝑘𝑗} 但参考书上采用了另外一种递归表达方式，有何不同？

本质上相同，但形式上给定了子问题的“序” Now,letbe the minimum weight of any path from vertexito vertexthat 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, 0 ifi=j. fi≠j =min(,ng-+0 1<k<n 问题1： 在有10个点的图中，岛=7的直观含义是什么？ 如果=7，能认定ij节点间的最短路径长度是7吗？

本质上相同，但形式上给定了子问题的“序” 问题1： 在有𝟏𝟎个点的图中，𝒍𝒊𝒋 𝟔 = 𝟕的直观含义是什么？ 如果𝒍𝒊𝒋 𝟔 = 𝟕,能认定ij节点间的最短路径长度是7吗？

本质上相同，但形式上给定了子问题的“序” 间题2： 如果定义矩阵L=(),L,L2,…,L-1 分别表示什么含义？

本质上相同，但形式上给定了子问题的“序

本质上相同，但形式上给定了问题的解 间题3： 如果定义矩阵L=(),L-1中的元素 L1表示什么含义？ In-1=In =In+i

本质上相同，但形式上给定了问题的解 𝐿 𝑛−1 = 𝐿 𝑛 = 𝐿 𝑛+1 …

一种“最优解”的递归定义方式 怎么从路-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去计算𝑙 𝑖𝑗 𝑚

自底向上计算 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' 哪里？

自底向上计算 𝑶(𝒏𝟑)