河池学院：《数据结构》课程电子教案（PPT教学课件）第8章 图 8.5 最短路径

从一顶点到另一顶点存在着一条路径时，称该路径长度为该路径上所 经过的边的数目，它等于该路径上的顶点数减1。 从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数 可能不同，即路径长度不同，把路径长度最短（即经过的边数最少） 的那条路径叫做最短路径，其路径长度称为最短路径长度或最短距离。 不带权图 采用广度优先遍历可以求最短路径 1/46

把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径 长度。 从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为 最短路径，其路径长度（权值之和）称为最短路径长度或者最短距离。 带权图 采用广度优先遍历可以求最短路径：不适合 2/46

提出“goto有害论” 提出信号量和PV原语 解决了“哲学家聚餐”问题 Dijkstra最短路径算法和银行家算法的创造者 第一个Algol 60编译器的设计者和实现者 THE操作系统的设计者和开发者 1972年获得图灵奖 与D.E.Knuth并称为我们这个时代最伟大的计算机科学家的人，与癌症抗 争多年，于2002年8月6日在荷兰Nuenen自己的家中去世，享年72岁 Edsger Wybe Dijkstra 1930年5月11日~2002年8月6日 3/46

1. 归并排序，快速排序和堆排序 2. 傅立叶变换与快速傅立叶变换 3. Dijkstra算法 4. RSA算法（一种加密算法） 5. 安全哈希算法 6. 整数因式分解 7. 链接分析（Google的Page Rank算法） 8. 比例积分微分算法 9. 数据压缩算法（以哈夫曼算法为基础） 10. 随机数生成算法 4/46

1. 狄克斯特拉算法过程 v 源点 u 其他顶点 最短路径和长度 单源最短路径算法 5/46

给定一个带权图G和一个起始点即源点v，狄克斯特拉算法的具体步骤如下： （1）初始化：顶点集S只包含源点，即S={v}，顶点v到自已的最短路 径长度为0。顶点集U包含除v外的其他顶点，源点v到U中顶点i的最短路径 长度为边上的权值（若源点v到顶点i有边）或∞（若源点v到顶点i 没有边，此时认为有一条长度为∞的最短路径）。 v j S U=V-S i 6/46

（2）从U中选取一个顶点u，它是源点v到U中最短路径长度最小的顶点， 然后把顶点u加入S中（此时求出了源点v到顶点u的最短路径长度）。 v i S U=V-S u 7/46

（3）以顶点u为新考虑的中间点，修改顶点u的出边邻接点j的最短路 径长度，此时源点v到顶点j的最短路径有两条，即一条经过顶点u，一条 不经过顶点u。 ① 若经过顶点u的最短路径长度比不经过顶点u的最短路径长度更短， 则修改源点v到顶点j的最短路径长度为经过顶点u的那条长度。 ② 否则，说明原来的不经过顶点u的最短路径长度更短，不需要修改。 v j u cvu wuj cvj 有一条路径 有一条边 （4）重复步骤（2）和（3）直到S包含所有的顶点即U为空。 两条路径中求最小者 8/46

2. 狄克斯特拉算法设计 狄克斯特拉算法设计要点： 判断顶点i属于哪个集合，设置一个数组S，S[i]=1表示顶点i属于S 集合，S[i]=0表示顶点i属于U集合。 保存最短路径长度，由于源点v是已知的，只需要设置一个数组 dist[0.n-1]，dist[i]用来保存从源点v到顶点i的最短路径长度。 dist[i]的初值为边上的权值，若顶点v到顶点i没有边，则 权值定为∞。以后每考虑一个新的中间点u时，dist[i]的值可能被 修改变小。 保存最短路径，设置一个数组path[0.n-1]，其中path[i]存放从 源点v到顶点i的最短路径。 9/46

为什么能够用一个一维数组保存多条最短路径呢？ path[j]只保存源点v到顶点j的最短路径上顶点j的前驱顶点 v . u j path[j]=u 如果该路径恰好包含源点v到u的最短路径  OK 如果不是   10/46