图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径最短路径 最短路径 ( ( Shortest Path) Shortest Path) n n 最短路径问题： 最短路径问题： 如果从图中某一顶点 如果从图中某一顶点 ( ( 称为 称为 源点 源点 ) ) 到达另一顶点 到达另一顶点 ( ( 称为终点 称为终点 ) ) 的路径可能 的路径可能 不止一条，如何找到一条路径，使得沿此 不止一条，如何找到一条路径，使得沿此 路径各边上的权值总和达到最小。 路径各边上的权值总和达到最小。 n n 问题解法 问题解法 单源最短路径 单源最短路径 Dijkstra Dijkstra 算法 算法 任意顶点对之间的最短路径 任意顶点对之间的最短路径 Floyd Floyd 算法 算法单源最短路径问题 单源最短路径问题 n n 问题的提出： 问题的提出： 给定一个带权有向图 给定一个带权有向图 G G 与源点 与源点 v v ， ， 求从 求从 v v 到 到 G G 中其它顶点的最短路径。 中其它顶点的最短路径。 限定各边上 限定各边上 的权值大于或等于 的权值大于或等于
