数据结构 第十九讲 最短路径.ppt

第十九讲最短路径 在日常生活中常会遇到这样的问题 从甲地到乙地是否有通路 哪条路最短 有向带权图中的最短路径问题 即求两个顶点之间长度最短的路径 也即边上权值之和最小的路径 在带权有向图中 称路径上的第一个顶点为源点 最后一个顶点为终点 一 单源最短路径 单源点的最短路径问题 给定带权有向图G和源点v 求从v到G中其余各顶点的最短路径 迪杰斯特拉 Dijkstra 算法 按路径长度递增的次序产生最短路径 此算法把网中所有顶点分成两个集合 凡以V1为源点 已经确定了最短路径的终点并 入S集合 S集合的初态应只包含V1 另一个集合T则是尚未确定最短路径的顶点的集合 T集合的初态应包含网中除V1的以外的所有的顶点 按各顶点与V1间的最短路径长度递增的次序 逐个把集合T中的顶点加入S集合中去 使得从V1到S集合中顶点的路径长度始终不大于从V1到T集合中各顶点的路径长度 算法中引进了一个辅助向量dist 它的某个分量dist i 表示当前求出的从V1到顶点i的最短路径长度 它的初始状态是邻接矩阵中第V1行的各列的值 显然从V1到各顶点的最短路径长度中最短的一条应该是dist u min dist i i V G 第一次求得的这条最短路径必然是 V1 u 这时 顶点u应从T集合中删掉 并入S集合中 每当选出一个顶点u并入集合S后 修改T中的最短路径dist 对于T中的某个顶点i而言 它的最短路径只能是 V1 i 或是 V1 u i 而不可能是其它情况 即 若dist u cost u i dist i 则dist i dist u cost u i 当T中各顶点的路径长度修改后 再从中选出一个路径长度最短的顶点 从T集合中删除 并入S集合 依次类推 就能求出从V1到所有顶点的最短路径长度 还要设置一个路径向量Path n 其中Path i 1 表示从源点到顶点i的最短路径上该点的前驱顶点 算法结束前 可根据找到源点到顶点i的最短路径上每个顶点的前驱顶点 从而得到从源点到i顶点的最短路径 1 2 5 3 4 6 45 50 10 35 30 20 15 10 20 15 3 具体算法如下 floatdist n intpath n S n DIJKSTRA floatcost n intv inti j k v1 pre intmin max 60 inf 80 v1 v for i 0 i n i dist i cost v1 i if dist i max path i v1 elsepath i 0 for i 0 i n i S i 0 S V1 1 dist v1 0 for i 0 i n 1 i min inf for j 0 j n j if S j S k 1 for j 0 jdist k cost k j dist j dist k cost k j paht k 1 for i 0 i n i printf dist i i 1 pre path i while pre 0 printf pre pre path pre 1 DIJKSTRADijkstra算法的时间复杂度为O n2 空间复杂度为O n 二 每一对顶点间的最短路径方法一 对于给定的有向网G V E 要对G中任意两个顶点u v 找出u到v的最短路径 我们可以利用Dijkstra算法 把每个顶点作为源点重复执行n次即可求出有n个顶点的有向网中每对顶点间的最短路径 时间复杂度为O n3 方法二 弗洛伊德 Floyed 算法在此算法中 以邻接矩阵cost表示有向带权图G 有向图中的n个顶点从1开始编号 算法中设立两个矩阵 分别用来存放各顶点的路径和相应的路径长度 矩阵path表示路径 矩阵A表示路径长度 初始时 设网的代价矩阵cost为A矩阵的初始值 可暂定为A 0 若要求最段路径 需要进行n次试探 对于从顶点i到顶点j的最段路径长度 首先让路径经过顶点1 比较路径和 取短的为当前求得的最段路径长度 对每一对最 段路径都做这样的试探 即可求得A 1 即A 1 是考虑了各顶点除了直接到达外还可经过顶点1再到达终点 然后再考虑在A 1 基础上让路径经过顶点2 求得A 2 依次类推 直到求得A n 为止 一般情况下 若从顶点i到顶点j的路径经过顶点k可以使路径变短的话 则修改A k i j A k 1 i k A k 1 k j 因此 A k i j 就是当前求得的从顶点i到顶点j的最短路径长度 且对应的p矩阵上的顶点序号均不大于k 这样经过n次试探 最后 求得的A n 就是各顶点间的最短路径长度 相应的P矩阵即为每对顶点间的最短路径上的顶点 初始时 矩阵P的各元素均赋值为0 表示每一对顶点之间都是直接达到的 中间不经过任何一个顶点 以后当让路径经过某个顶 点k时 如果使路径更短 则在修改A k i j 的同时 令P i j k 即若P i j 0 则其中存放的是从顶点i到顶点j的路径上经过的某个顶点 那么如何求出从顶点i到顶点j的路径上的全部顶点呢 则只需递归地去查P i k 和P k j 直到其值为0为止 该递归过程为 path intp n n inti intj k p i 1 j 1 if k 0 path p i k printf k path p k j Floyed算法的具体过程如下 Floyed floata n n floatcost n n intp n n inti j k for i 0 i n i for j 0 j n j a i j cost i j p i j 0 for k 0 k n