数据结构第18讲第7章图-6,7节.ppt

7.8 最短路径问题 1. 从源点到其余各点的最短路径 迪杰斯特拉算法的基本思想: 依最短路径的长度递增的次序求得各条路径 第1条最短路径是从源点V0出发到达一个邻接点Vi的边; 第2条最短路径或者是从源点V0出发到达另 一个邻接点Vj的边，或者是从源点V0出发，经 过顶点Vi 到达的顶点Vj的路径； 第3条最短路径或者是从源点V0出发到达另 一个邻接点Vk的边，或者是从源点V0出发，经 过顶点Vi 和Vj到达的顶点Vk的路径； 进行n-1次计算后算法结束。 求最短路径的迪杰斯特拉算法： 一般情况下， Dist[k] 或者 + 初值： Dist[k] ＝ G.arcs[V0][k] 2. 设置辅助数组Dist，其中每个Dist[k] 记录当前所求得的从源点V0到顶点 k 的最短距离值。 1. 设一个集合final[]，保存已求得最短路径的终点序号，其初值为false； 3. 设一个数组p[ ]，存放在最短路径上该顶点的前一个顶点的顶点号,Dist修改后p也要修改； final dist F F F F F 8 8 8 3 30 V0 V1 V2 V3 V4 V0 V1 V4 V2 V3 3 8 25 4 12 20 5 30 10 迪杰斯特拉算法执行过程 0 1 2 3 4 0 1 2 3 4 20 4 0 12 0 3 2 3 30 0 0 25 8 4 0 1 0 3 10 5 1 2 3 0 8 8 8 8 8 8 8 8 8 8 8 0 0 0 0 0 V0 T 0 T V1 28 11 T V3 15 23 P V2 V0 T T 0 v0 v0 v0 v0 0 v0 v1 v1 v0 0 v0 v3 v1 v3 void ShortestPath_DIJ Mgraph G,int V0 初始化 p []; final[ ]; dist[ ]; for i 1, i G.vexnum;++ i //循环n－1次 min INFINITY; for w 1, w G.vexnum;++ w //在没有求出最短距离的 if !final[w] //顶点中找距V0最近的顶点v if dist[w] min v w; min dist[w] final[v] True ; //离最近的顶点V加入final集 for w 1, w G.vexnum;++ w //更新不在final中顶点的当前最短路径 if !final[w] min+G.arcs[v][w] dist[w] //当前dist[w]大 dist[w] min+ G.arcs[v][w]; //修改dist[w] p [w]＝v; //顶点w的前一个顶点是v //for //for 时间复杂度 O n2 作 业 基础知识：7.10, 7.11, 7.13, 算法题： 7.41, 7.42 * 7.1 图的抽象数据类型定义 7.2 图的存储表示 7.3 图的遍历 7.4 最小生成树 7.5 重（双）连通图和关节点 7.8 最短路径问题 7.6 拓扑排序 7.7 关键路径 第七章 图 A C B D E F 有向无环图 7.6 拓扑排序 如何判断一个图是否存在环 回路 对无向图---深度优先遍历。 对有向图----拓扑排序。 A C B D E F 无向有环图 课程编号 课程名称 C1 程序设计基础 C2 离散数学 C3 数据结构 C4 汇编语言 C5 语言的设计和分析 C6 计算机原理 课程编号 课程名称 C7 编译原理 C8 操作系统 C9 高等数学 C10 线性代数 C11 普通物理 C12 数值分析 C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8 C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8 C12 C1 C9 C7 C8 C4 C2 C3 C10 C11 C5 C6 AOV网 Activity On Vertex 顶点表示活动, 弧表示优先关系 何谓“拓扑排序”？ 对有向图进行如下操作: 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。 由此所得顶点的线性序列称之为拓扑有序序列 例如：对于下列有向图 B D A C 可求得拓扑有序序列： A B C D 或 A C B D B D A C 对于下列有向图 不能求得它的拓扑有序序列。 因为图中存在一个回路 B, C, D 结论