计算机问题求解一论题3-9 All-Pair Shortest Paths 2016年11月2日
计算机问题求解 – 论题3-9 - All-Pair Shortest Paths 2016年11月2日
复习 ■动态规划的解题基本规律是什么？ 口最优子结构分析 口递归定义最优解 口设计自底向上算法依次求解
复习 动态规划的解题基本规律是什么？ 最优子结构分析 递归定义最优解 设计自底向上算法依次求解
最优子结构 假设这是从到的最短通路，经过k If vertices i andare distinct,then we decompose path p into iwhere path pnow contains at most m-l edges.By Lemma 24.1. p'is a shortest path fromitok,ands)=(ik)j
i k j 假设这是从i到j的最短通路，经过k 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, 98 ifi=j, fi卡j. For mwe computeas the minimum of(the weight of a shortest path from i to j consisting of at most m-I 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 of j.Thus,we recursively define min (份”mng+0) 1<k< min +w (25.2) 1<k≤别 The latter equality follows since w=0for all j
递归定义最优解
问题1： 作：行10个的，的i观义是什么？ 如果=7，能认节点间的最短路径长度 是7吗？