最短路径算法.ppt

8 3单源最短路径 给定带权有向图G V E 其中每条边的权是非负实数 另外 还给定V中的一个顶点 称为源 现在要计算从源到所有其它各顶点的最短路长度 这里路的长度是指路上各边权之和 这个问题通常称为单源最短路径问题 1 算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法 8 3单源最短路径 其基本思想是 设置顶点集合S并不断地作贪心选择来扩充这个集合 一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知 初始时 S中仅含有源 设u是G的某一个顶点 把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径 并用数组dist记录当前每个顶点所对应的最短特殊路径长度 Dijkstra算法每次从V S中取出具有最短特殊路长度的顶点u 将u添加到S中 同时对数组dist作必要的修改 一旦S包含了所有V中顶点 dist就记录了从源到所有其它顶点之间的最短路径长度 8 3单源最短路径 例如 对右图中的有向图 应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中 8 3单源最短路径 Dijkstra算法的迭代过程 初始状态下 S中只有一个点 源点v1 s distance path 第二步 将S外距离S最近的点v2加入S 更新相应信息 s distance path 1 60 2 第三步 将S外距离S最近的点v4加入S 更新相应信息 s distance path 1 50 4 90 4 第四步 将S外距离S最近的点v3加入S 更新相应信息 s distance path 1 60 3 第五步 将S外距离S最近的点v5加入S 更新相应信息 s distance path 1 voidDijkstra intG N intv0 intdistance intpath intn 源点v0到其他顶点的最短距离distance和最短路径下标path int s newint n intminDis i j u 初始化三个数组 逐次将各点加入S 在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u 标记顶点u已从集合T加入到集合S中 修改从v0到其他顶点的最短距离和最短路径 voidDijkstra intG N intv0 intdistance intpath intn 从源点v0到其他顶点的最短距离distance和最短路径下标path int s newint n intminDis i j u 初始化三个数组for i 0 i n i distance i G v0 i s i 0 if I v0j if s j 0j if s j 0 G u j MAX distance u G u j distance j distance j distance u G u j path j u 2 算法的正确性和计算复杂性 1 贪心选择性质 2 最优子结构性质 3 计算复杂性对于具有n个顶点和e条边的带权有向图 如果用带权邻接矩阵表示这个图 那么Dijkstra算法的主循环体需要时间 这个循环需要执行n 1次 所以完成循环需要时间 算法的其余部分所需要时间不超过 7 5所有点对的最短路径问题 对于一个各边权值均大于0的有n个顶点的带权有向图G V E 求所有顶点之间的最短路径和最短距离 图的邻接矩阵表示法 3 V b a 2 9 6 123 L 029061 0 复习Dijkstra算法 其基本思想是 设置顶点集合S并不断地作贪心选择来扩充这个集合 一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知 初始时 S中仅含有源点 设u是G的某一个顶点 把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径 并用数组distance记录当前每个顶点所对应的最短特殊路径长度 Dijkstra算法每次从V S中取出具有最短特殊路长度的顶点u 将u添加到S中 同时对数组distance作必要的修改 一旦S包含了所有V中顶点 distance就记录了从源到所有其它顶点之间的最短路径长度 算法中 我们不断更新以下三个数组 s数组 s i 当顶点i加入S时 s i 置1Distance数组 Distance i 记录原点到顶点i的最短特殊路径长度 path数组 path i 记录顶点i在其最短特殊路径上的前驱顶点 由该数组可求得原点到各点的最短路径 如 设源点是顶点1 path数组如下 例如 对右图中的有向图 应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中 s distance path 由源点1到顶点5的路径为 1 4 3 5 方法一 重复调用Dijkstra算法n次 可轮流以每一个顶点为源点 重复调用狄克斯特拉算法函数Dijkstra n次 即可求得所有顶点之间的最短路径和最短距离 利用Dijkstra 函数求所有顶点之间的最短路径算法如下 其中 distance i j 中存放着从顶点i到顶点j的最短距离 path i j 中存放着从顶点i到顶点j的最短路径的前一顶点下标 voidShortPath AdjMWGraph 由于狄克斯特拉算法的时间复杂度是O n2 所以n次调用狄克斯特拉算法的时间复杂度是O n3 该问题具有最优子结构性质 例如上图中 若路线I和J是A到C的最优路径 则根据最优化原理 路线J必是从B到C的最优路线 子问题的构造 原问题 每个顶点到其他所有顶点的最短距离最小的子问题D0 从顶点i 不得经过任何其他顶点 到顶点j的距离 子问题D1 从顶点i 可以经过顶点1 不得经过其他任何其他顶点 到顶点j的距离 子问题Dk 从顶点i 可以经过顶点1 顶点2 顶点k 不得经过任何其他顶点 到顶点j的距离 子问题Dn 从顶点i 可以经过顶点1 顶点2 顶点n 到顶点j的距离 即原问题 递推关系的建立 由di jk 1推出di jk的过程如下若k 0 di jk L i j 因为从i到j不允许经过任何其他顶点 若1 k n di jk min di jk 1 di kk 1 dk jk 1 子问题Dk 1 从顶点i 可以经过顶点1 顶点2 顶点k 1 到顶点j的距离 子问题Dk 从顶点i 可以经过顶点1 顶点2 顶点k 1 顶点k 到顶点j的距离 从子问题Dk 1 到子问题Dk 仅仅多考虑了一个顶点k 我们需要重新考虑从i到j的距离 顶点i到顶点j 是不是从k走会更近 如果从顶点i到顶点j从顶点k走更近 则i到j的距离di jk i到k的距离di kk 1 k到j的距离dk jk 1如果顶点i到顶点j从顶点k走更远 甚至走不通 则保持原来的距离不变di jk di jk 1 由di jk 1推出di jk的过程 主要考虑的是顶点k的加入会引起什么变化 由不允许路过顶点k到允许路过顶点k 有些点间的距离是否会变的更近 例 考虑下图所示的带权有向图 求所有顶点之间的最短距离 V b a 123 L 计算过程 Di jk 从顶点i 可以经过顶点1 顶点2 顶点k 到顶点j的距离 在D1中 第1行和第一列是不变的 因为说从顶点1到顶点j或顶点j到顶点1 允许经过顶点1是没有意义的 D1 2 3 从顶点2到顶点3的距离 可以经过顶点1 1 不经过顶点1 仍是D0 2 3 6 2 过顶点1 D0 2 1 D0 1 3 8 9 17取最小值6 D1 3 2 从顶点3到顶点2的距离 可以经过顶点1 1 不经过顶点1 仍是D0 3 2 2 过顶点1 D0 3 1 D0 1 2 1 2 3取最小值3 D2 1 3 从顶点1到顶点3的距离 也可以经过顶点2 1 不经过顶点2 仍是D1 1 3 9 2 过顶点2 D1 1 2 D1 2 3 2 6 8取最小值8 算法设计 重要发现 在从Dk 1到Dk的计算过程中中 第k行和第k列是不变的 因为说从顶点k到顶点j或顶点j到顶点k允许经过顶点k是没有意义的 而在从Dk 1到Dk的计算过程中也只用到第k行和第k列 也就是说 在这一步的计算过程中用到的