第五章图(四)

1、第七讲 图浙江大学 陈 越6.6 最短路径问题 若用带权图表示交通网，图中顶点表示地点，边代表两地之间有直接道路，边上的权值表示路程(或所花费用或时间) 。从一个地方到另一个地方的路径长度表示该路径上各边的权值之和。问题： 两地之间是否有通路? 在有多条通路的情况下，哪条最短? 考虑到交通网的有向性，直接讨论的是带权有向图的最短路径问题，但解决问题的算法也适用于无向图。 将一个路径的起始顶点称为源点，最后一个顶点称为终点。问题分类单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径（有向）无权图（有向）有权图多源最短路径问题：求任意两顶点间的最短路径6.6.1无权图的单源最短路算法

2、按照递增（非递减）的顺序找出固定顶点到各个顶点的最短路.Dijkstra算法（迪杰斯特拉）1.无权图的单源最短路算法0 v31 v1v42v2 2v5 30: 1: 2: v3v1 and v6v2 and v41 v6v7 33: v5 and v7在无权图中，经过顶点最少的路就是最短路。2.有权图的单源最短路算法从v1出发到v6的最短路径是：权重和最小的按照递增的顺序找出到各个顶点的最短路课本例题6.17用Dijkstra网图6.30中v0到所有其余顶点的最短路径。这是一个按距离递增的顺序逐步找出v0到所有其余顶点的最短路径的过程.D 表示存储v0到其余顶点的“当前最短距离”P 对应的最短

3、路径邻接于哪那个顶点初始时（第0步），数组D就是该图邻接矩阵表示时v0对应的行向量在D中选择到v0距离最小的顶点v1，可以断定，顶点v1已经找到了到v0的最短距离。因此， v1作为已经求得最短路径的顶点，通过绕行v1 ， v0到其余顶点的当前最短距离很可能更短。选v1 （第1步），考虑v1的邻接点v2和 v3（不需考虑已经求得最短距离的v0 ，D1用灰色表示，不参与下一步最短路径的选择） 因此，在数组D中选择到 v0距离最小的顶点v3 ，通过绕行v3 ， v0到其余顶点的当前最短距离很可能更短。选v3 （第2步），考虑v3的邻接点v5和 v6（不需考虑已经求得最短距离的v1和 v3 ，D1和D

4、3用灰色表示，不参与下一步最短路径的选择） 因此，在数组D中选择到 v0距离最小的顶点v6 ，通过绕行， v0到其余顶点的当前最短距离很可能更短。选v6 （第3步），考虑v6的邻接点v5和 v8（不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 ，不参与下一步最短路径的选择） 因此，在数组D中选择到 v0距离最小的顶点v2 ，通过绕行， v0到其余顶点的当前最短距离很可能更短。选v2 （第4步），考虑v2的邻接点v5和 v4（不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2 ，不参与下一步最短路径的选择） 因此，在数组D中选择到 v0距离最小的顶点v5 ，通过绕行

5、， v0到其余顶点的当前最短距离很可能更短。选v5 （第5步），考虑v5的邻接点v4、 v8和 v7（不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2 、 v5 ，不参与下一步最短路径的选择） 因此，在数组D中选择到 v0距离最小的顶点v4 ，通过绕行， v0到其余顶点的当前最短距离很可能更短。选v4 （第6步），考虑v4的邻接点 v7（不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2 、 v5 、 v4 ，不参与下一步最短路径的选择） 因此，在数组D中选择到 v0距离最小的顶点v8 ，通过绕行， v0到其余顶点的当前最短距离很可能更短。选v8 （第7步

6、），考虑v8的邻接点 v7和v9 （不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2 、 v5 、 v4 、 v8 ，不参与下一步最短路径的选择） 因此，在数组D中选择到 v0距离最小的顶点v7 ，通过绕行， v0到其余顶点的当前最短距离很可能更短。选v7 （第8步），考虑v7的邻接点 v9 （不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2 、 v5 、 v4 、 v8 、 v7 ，不参与下一步最短路径的选择） 因此，在数组D中选择到 v0距离最小的顶点v9 。选v9 （第9步）。（不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2

7、、 v5 、 v4 、 v8 、 v7 ，不参与下一步最短路径的选择） D1-D9表示从v0到v1-v9 的最短距离。通过搜索数组P得到最短路径，比如，v0到v9的最短路径可以这样得到：P9=7，P7=4，P4=5，P5=3，P3=1，P1=0，顺序到过来就是：v0，v1，v3 ，v5，v4，v7，v9.Dijkstra 算法令S=源点s + 已经确定了最短路径的顶点vi对任一未收录的顶点v，定义distv为s到v的最短路径长度，但该路径仅经过S中收集的顶点。即路径s(viS)v的最小长度若路径是按照递增（非递减）的顺序生成的，则真正的最短路必须只经过S中的顶点。每次从未收录的顶点中选一个di

8、st最小的收录增加一个v进入S，可能影响另外一个w的dist值！（v一定是s到w的路径上，v一定与w有一条直接的边）distw = mindistw, distv + 的权重的权重6.6.2多源最短路算法方法1：直接将单源最短路算法调用|V|遍T = O( |V|3 + |E|V|)方法2：T = O( |V|3 )对于稀疏图效果好算法对于稠密图效果好课本例题6.19用Floyd网图6.31中每一对顶点之间的最短路径。 带权有向图及其带权有向图及其邻接邻接矩阵矩阵 0 6 114 0 2 3 0V12116V2V034最后得到的每对顶点之间的最短路径长度及其最短路径都应该分别是一个二维矩阵，分

9、别用二维数组D和二维数组P表示。Dij表示从vi到vj的最短路径长度，Pij表示从vi到vj的最短路径上vj的父顶点号。第一步 查看v0：0行0列以外的非对角元素，D12=2垂直和水平方向分别向0列0行投影两个元素之和D10+D02=4+11=15，因为152，所以D12=2保持不变。D21=，垂直和水平方向分别向0列0行投影两个元素之和D01+D20=3+6=9，因为93，所以D20=3保持不变。D02=11，垂直和水平方向分别向1列1行投影两个元素之和D01+D12=6+2=8，因为86，所以D01=6保持不变。D10=4，垂直和水平方向分别向2列2行投影两个元素之和D12+D20=2+3

10、=5，因为45,保持不变。下面考察最短路径矩阵P，与D的演变过程相对应：Pij=i的含义是：从vi到vj的最短路径中，vj的前驱结点（父结点）为vi，即初始假设直接的边就是最短路径。102100112多源最短路算法Floyd 算法Dkij = 路径 i l k j 的最小长度的最小长度D0, D1, , D|V|-1ij即给出了即给出了i到到j的真正最短距离的真正最短距离最初的D-1是什么？当Dk-1已经完成，递推到Dk时：或者k 最短路径 i l k j ，则，则Dk = Dk-1或者k 最短路径 i l k j ，则该路径必定由两，则该路径必定由两段最短路径组成： Dkij=Dk1ik+D

11、k1kj0123452030606515201080403570图图 带权有向图及其带权有向图及其邻接邻接矩阵矩阵 20 60 10 65 30 70 40 35 20 15 80 表表 求最短路径时数组求最短路径时数组dist和和pre的各分量的变化情况的各分量的变化情况 初始化为Pathij=-1，表示从Vi到Vj 不经过任何(S中的中间)顶点。当某个顶点Vk加入到S中后使Aij变小时，令Pathij=k。 下表给出了利用Floyd算法求图的带权有向图的任意一对顶点间最短路径的过程。图图 带权有向图及其带权有向图及其邻接邻接矩阵矩阵 0 2 8 0 4 5 0V1482V2V05 表表 用用Floyd算法求任意一对顶点间算法求任意一对顶点间最短路径最短路径 0 2 8 0 45 0 0 2 8 0 4 5 7 0 0 2 6 0 4 5 7 0 0 2 6 9 0 4 5 7 0A -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 1 2 -1 -1 -1 0 -1PathS 0 0, 1 0, 1, 2 步骤步骤初态初态k=0K=1K=2根据上述