图论第09讲 阙夏制作(免费).ppt

图论Graphic Theory 第三章 图的算法 §1 最短路径问题及算法 §2 任意两点间最短路径及其算法 §3 图的遍历算法 §4 图的块划分 内容回顾 Bellman-Ford算法 （1）任取一棵以v0为根的生成树，在每个顶点标出v0到该点的长度li； （2）设树枝之外的边vij的长度为dij，依次检查每条树外的边，若对其中一对邻接点vi， vj出现：lj＞li＋ dij，则去掉以vj为终点的树枝，用vij代替； （3）重复（2），直到所有树外的边都比较过为止。 内容回顾-1 Dijkstra算法 基本思想： 按照最短路径长度不减的次序求解各点的解。 即按由近到远的次序求解各顶点的解 内容回顾-2 Dijkstra算法描述（起点为v0）： （1）初始化： 若(v0,vi)存在，则li＝w (v0,vi)，否则li＝∞； （2）从未解的顶点中选择一个l值最小的顶点vk,则vk是已解顶点； （3）修改vk的直接后继顶点的l值 ——如果经过vk路径长度可以更近 （4）重复（2）、（3），直到所有顶点求解完毕。 §3-2 任意两点间最短距离及其算法 求解方法很多： 对每个顶点都执行Dijkstra算法； 动态规划算法： Floyd-Warshall算法 什么是动态规划算法？ 动态规划法设计算法一般分成三个阶段： (1)分段：将原问题分解为若干个相互重叠的子问题； (2)分析：分析问题是否满足最优性原理，找出动态规划函数的递推式； (3)求解：利用递推式自底向上计算，实现动态规划过程。 动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。 一、动态规划算法： 设A＝(aij)m×l， B＝(bij)l×n。 定义： C＝A⊙B＝ (cij)m×n， 其中cij＝min{ai1＋b1j，ai2＋b2j，…， ail＋blj} 设A＝(aij)m×n， B＝(bij)m×n。 定义： D＝A B＝ (dij)m×n 其中dij＝min{aij，bij} 一、动态规划算法：-1 利用刚才定义的运算求任意两点间的最短距离。 设D＝(dij)n×n是图G的距离矩阵，即dij表示边vi，vj边的长度。若vi，vj间无边，则dij＝∞。 一、动态规划算法：-2 这样，D(2)＝D⊙D＝(d(2)ij)n×n 其中d(2)ij=min{di1+d1j，di2+d2j，…，din＋dnj} ∴d(2)ij表示从vi出发两步可以到达vj的道路中距离最短者。 同理D(k)＝D(k-1)⊙D＝(d(k)ij)n×n ∴d(k)ij表示从vi出发k步可以到达vj的道路中距离最短者。 于是矩阵S＝D D(2) …… D(n)＝(sij)n×n 其中sij代表为vi到vj的所有道路中距离最短者。 一、动态规划算法：-3 求下图各点间的最短路径 一、动态规划算法：-4 求下图各点间的最短路径 一、动态规划算法：-5 类似可得： 一、动态规划算法：-5 ∴S＝D D(2) D(3) D(4) D(5) D(6) ＝(sij)6×6 二、Floyd-Warshall算法 Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。 基本思想： 通过求解矩阵序列A(0)，A(1)，…，A(n)来实现问题的求解。 二、Floyd-Warshall算法－1 其中： A(0)——图的距离矩阵； A(n)——最终解； a(0)ij——边(vi,vj)的权值 a(k)ij——从vi到vj在所经过的顶点号≤k最短路径长度。 即通过依次比较顶点修改路径实现求解的。 对于任意两个顶点vi，vj，对于新比较的顶点vk一旦出现a(k-1)ij＞aik＋akj，则修改对应的a(k)ij。 二、 Floyd-Warshall算法 -2 用Floyd算法求下图各点间的最短路径。 二、 Floyd-Warshall算法 -3 比较经过顶点号≤1的矩阵 二、 Floyd-Warshall算法 -4 比较经过过顶点≤ 2的矩阵 二、 Floyd-Warshall算法 -5 比较经过过顶点≤ 3的矩阵 二、 Floyd-Warshall算法 -6 比较经过过顶点≤ 4的矩阵 二、 Floyd-Warshall算法 -7 比较经过过顶点≤ 5