最短路径8.58.5.1最短路径的概念不带权图从一顶点到另一顶点存在着一条路径时，称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度称为最短路径长度或最短距离。采用广度优先遍历可以求最短路径1/46
从一顶点到另一顶点存在着一条路径时，称该路径长度为该路径上所 经过的边的数目，它等于该路径上的顶点数减1。 从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数 可能不同，即路径长度不同，把路径长度最短（即经过的边数最少） 的那条路径叫做最短路径，其路径长度称为最短路径长度或最短距离。 不带权图 采用广度优先遍历可以求最短路径 1/46
带权图把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径长度或者最短距离。采用广度优先遍历可以求最短路径：不适合2/46
把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径 长度。 从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为 最短路径，其路径长度（权值之和）称为最短路径长度或者最短距离。 带权图 采用广度优先遍历可以求最短路径：不适合 2/46
8.5.2狄克斯特拉算法Edsger wybeDijkstra1930年5月11日~2002年8月6日提出“goto有害论”提出信号量和PV原语解决了“哲学家聚餐”问题Dijkstra最短路径算法和银行家算法的创造者第一个Algol60编译器的设计者和实现者THE操作系统的设计者和开发者1972年获得图灵奖与D.E.Knuth并称为我们这个时代最伟大的计算机科学家的人，与癌症抗争多年，于2002年8月6日在荷兰Nuenen自己的家中去世，享年72岁3/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.傅立叶变换与快速傅立叶变换Dijkstra算法34.RSA算法（一种加密算法）安全哈希算法5.整数因式分解6.链接分析（Google的PageRank算法）7.8.比例积分微分算法9.数据压缩算法（以哈夫曼算法为基础随机数生成算法10.4/46
1. 归并排序，快速排序和堆排序 2. 傅立叶变换与快速傅立叶变换 3. Dijkstra算法 4. RSA算法（一种加密算法） 5. 安全哈希算法 6. 整数因式分解 7. 链接分析（Google的Page Rank算法） 8. 比例积分微分算法 9. 数据压缩算法（以哈夫曼算法为基础） 10. 随机数生成算法 4/46
1.狄克斯特拉算法过程最短路径和长度源点其他顶点单源最短路径算法5/46
1. 狄克斯特拉算法过程 v 源点 u 其他顶点 最短路径和长度 单源最短路径算法 5/46