AA-Chapter 8-02-动态规划.pdf

算法设计与分析 主讲：路永钢 ylu@lzu.edu.cn 第八章 动态规划 Dynamic programming 2 算法分析与设计 兰州大学信息学院 单源最短路径问题 • 有向无环图的最短路径问题 概念：给定一个有向无环图，求给定起始顶点到结束顶点 的最短路径，此即单源最短路径问题。 10 2 5 4 9 6 4 8 9 8 8 点 源 1 2 3 7 3 6 6 10点 收 10 4 3 5 9 8 4 4 7 3 单源最短路径问题 • 有向无环图的最短路径问题 概念：给定一个有向无环图，求给定起始顶点到结束顶点 的最短路径，此即单源最短路径问题。 10 2 5 4 9 6 4 8 9 8 8 点 源 1 2 3 7 3 6 6 10点 收 10 4 3 5 9 8 4 4 7 有向无环图的特点是所有节点可以线性化 （拓扑排序）, 使得所有边保持由左到右的方向。 4 单源最短路径问题 分段：顶点集分为k个不相交子集 Vd , 1≤d≤k , k≥2 , 级内顶点不相邻。任一条边 (u,v) ，u ∈V ，v ∈V ，m≥1 。 d d+m 分级 k = 1 k = 2 k = 3 k = 4 k = 5 计算方向 从源点到收 V1 V2 V3 V4 V5 10 点依次编号 2 5 4