计算机问题求解一论题3-9 All-Pair Shortest Paths 2020年11月17日
计算机问题求解 – 论题3-9 - All-Pair Shortest Paths 2020年11月17日
算法的输入形式 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 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,其间的 任意子路径均最短 这对我们未来的“递归”有什么启发？
一种“最优解”的递归定义方式 ■表达节点到的最短路径长度的动态规划递归表达式： 口1，T(i,j)=W 2.Z(i,j)=min1<=k<=n[(i,k)+W) 但参考书上采用了另外一种递归表达方式，有何不同？ 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, ifi=j, fi≠j =mn(”,盟-”+）
一种“最优解”的递归定义方式 ◼ 表达节点i到j的最短路径长度的动态规划递归表达式： ❑ 1，L(i,j)=wij ❑ 2, L(i,j)=min1<=k<=n{L(i,k)+wkj} 但参考书上采用了另外一种递归表达方式，有何不同？