知识点回顾 拓扑排序 关键路径 应用领域、求解步骤、算法实现过程 应用领域 求解步骤

Presentation on theme: "知识点回顾 拓扑排序 关键路径 应用领域、求解步骤、算法实现过程 应用领域 求解步骤"— Presentation transcript:

1 知识点回顾 拓扑排序 关键路径 应用领域、求解步骤、算法实现过程 应用领域 求解步骤
求Ve(i)、求Vl(j)、求e(i)、求l(i)、计算l(i)-e(i)

2 第六章 图 6.1 图的定义和术语 6.2 图的存储结构 6.3 图的遍历 6.4 图的连通性问题 6.5 有向无环图及其应用
6.6 最短路径

3 6.6最短路径 典型用途：求图的最短路径问题用途很广，例如：交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短? 交通网络可用带权有向图来表示。顶点表示城市名称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。如何能够使一个城市到另一个城市的运输时间最短或运费最省？这就是一个求两座城市间的最短路径问题。 问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径 （注：最短路径与最小生成树不同，路径上不一定包含n个顶点）

4 实例: v1 v2 v5 v3 v6 v4 v7 9 15 12 6 4 2 3 8 5 11 16 从v1到v7共有5条路径:
8 30 13 7 17 32 9 13 长度 最短路径 <V0,V1> <V0,V2> <V0,V2,V3> <V0,V2,V3,V4> <V0,V2,V3,V4,V5> <V0,V1,V6> 8 19 21 20

5 一、单源最短路径—用Dijkstra（迪杰斯特拉）算法
两种常见的最短路径问题： 一、单源最短路径—用Dijkstra（迪杰斯特拉）算法 二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法 一顶点到其余各顶点 任意两顶点之间

6 6.6.1单源点最短路径 单源点最短路径是指：给定一个出发点(单源点)和一个有向网G=(V，E),求出源点到其它各顶点之间的最短路径。
迪杰斯特拉(Dijkstra)在做了大量观察后,首先提出了按路径长度递增序产生各顶点的最短路径算法,我们称之为迪杰斯特拉算法。

7 迪杰斯特拉(Dijkstra)算法思想 按路径长度递增次序产生最短路径算法： 把V分成两组： （1）S：已求出最短路径的顶点的集合
（2）V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中， 保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度 依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 （反证法可证）

8 求最短路径步骤 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值
若存在<V0,Vi>，为<V0,Vi>弧上的权值 若不存在<V0,Vi>，为 从T中选取一个其距离值为最小的顶点W，加入S 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值 重复上述步骤，直到S中包含所有顶点，即S=V为止

9 5 1 6 4 3 2 8 30 13 7 17 32 9 终点 从V0到各终点的最短路径及其长度 V1 V2 V3 V4 V5 V6 Vj 13 <V0,V1> 8 <V0,V2>  30 <V0,V4> 32 <V0,V6> V2:8 13 <V0,V1> <V0,V2,V3> 30 <V0,V4>  32 <V0,V6> V1:13 13 <V0,V2,V3> 30 <V0,V4> 22 <V0,V1,V5> 20 <V0,V1,V6> V3:13 19 <V0,V2,V3,V4> 22 <V0,V1,V5> 20 <V0,V1,V6> V4:19 21 <V0,V2,V3,V4,V5> 20 <V0,V1,V6> V6:20 <V0, V1,V6>

10 算法实现 图用带权邻接矩阵存储ad[][] 数组dist[]存放当前找到的从源点V0到每个终点的最短路径长度，其初态为图中直接路径权值
数组pre[]表示从V0到各终点的最短路径上，此顶点的前一顶点的序号；若从V0到某终点无路径，则用0作为其前一顶点的序号

11 1 1 1 1 1 1 算法分析：T(n)=O(n²) 算法描述 dist 1 2 3 4 5 6 7 0 13 8  30  32
  32 pre (1) k=1 1 6 2 7 5 4 3 1 8 30 13 17 32 9 1 1 1 1 1 长度 最短路径 13 19 22 21 20 <V1,V2> 13 <V1,V3> 8 3 4 5 2 2 <V1,V3,V4> 13 <V1,V3,V4,V5> 19 <V1,V3,V4,V5,V6> 21 <V1,V2,V7> 20 算法分析：T(n)=O(n²)

12 每一对顶点之间的最短路径 方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次—— T(n)=O(n³)
方法二：弗洛伊德(Floyd)算法 算法思想：逐个顶点试探法 求最短路径步骤 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值；否则为 逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值 所有顶点试探完毕，算法结束

13 例 A C B 2 6 4 3 11 3  0 初始： 路径： AB AC BA BC CA 加入A： 路径： AB AC BA BC CA CAB 加入B： 路径： AB ABC BA BC CA CAB 加入C： 路径： AB ABC BCA BC CA CAB

14 算法实现 算法描述 图用邻接矩阵存储 length[][]存放最短路径长度 path[i][j]是从Vi到Vj的最短路径上Vj前一顶点序号
初始： 3  0 length= path= 例 1 3 2 6 4 11 加入V1： length= path= 加入V2： length= path= 加入V3： length= path= 算法分析：T(n)=O(n³)

15 第七章 小结 图 Dijkstra算法 最短路径 Floyd算法 拓扑排序 邻接矩阵 有向图的应用 DAG图 关键路径 邻 接 表 存储结构
第七章 小结 Dijkstra算法 最短路径 Floyd算法 拓扑排序 邻接矩阵 有向图的应用 DAG图 关键路径 邻 接 表 存储结构 十字链表 邻接多重表 图 应用 深度优先搜索 遍 历 广度优先搜索 图的连通分量 （利用DFS） 无向图的应用 Prim算法 图的生成树 最小生成树 Kruskal算法

16 有向图如下图，求V0到其它各顶点的最短路径。
作业： 有向图如下图，求V0到其它各顶点的最短路径。 ０ １ ２ 3 4 5 100 10 50 30 60 20