1、 数据结构课程设计 设计题目：图顶点间最短路径算法 专 业：计算机科学与技术 班 级： 姓 名： 学 号： 指 导 老 师： 完 成 时 间：2009-5-9 一：需求分析： 1 问题描述：路径问题在图论中占有重要位置，因为这与日常生活中的许多问题有着广泛 的联系。比如乘汽车旅行时，我们总希望找出到目的地尽可能短的线路；如果在地图上 标出每两个路口之间的距离，如何找出一条最短的行车路线？在这个例子中我们可以把 地图模型化为一个图，结点表示一段公路的起点和终点，边的权值表示公路的长度。我 们的目标是从起点出发找出一条到达目的地的最短路径。一种直接的方法就是列举出所 有的路径，并计算出每条路径的长
2、度，然后选择最短的一条。容易看出，即使不考虑包 含回路的路径，在起点和终点之间依然可能存在很多不同的行车路线，而其中绝大多数 是不必考虑的。 二：概要设计 1 设计思想： Dijkstra 算法的基本思想： 这种算法是解决有向图的最短路径问题的条件是该图所有边的权值是非负值。 Dijkstra 算 法定义了一结点集合， 从源结点到集合是任一点的最短路径的权值均已确定。 算法反复地从 集合中挑选出其最短路径估计为最小的结点， 并将最小结点插入集合， 并对和最小结点相邻 的所有边进行松弛。 Bellman-ford 算法的基本思想： Floyd 能在边的权值为负的情况下解决单源最短路径问题。已知有
3、向加权图 G=（V，E） ，设 其源结点为 S，加权函数 w：ER，对该图运行 FLOYD 算法可返回一布尔值，表有图中是否 存在一个从源结点可达的权值为负的回路。如果存在这样的回路，则算法返回 FLASE，说明 该问题无解。 若不存在这样的回路， 算法将产生最短路径及其权值 Floyd 算法运用了松弛技 术， 对每一个结点Vv 并逐步减小从源s到v的最短路径的权值的估计值)(vd直至达到 实际的最短路径),(vs. Floyd 算法基本思想： 设带权图 G=(V,E)，有 N 个顶点，图采用邻接矩阵作为存储结构。Floyd 算法是以关 系矩阵为基础， 把关系矩阵看成是没有经过任何中间结点，
4、直接可以到达的每一对顶点间的 最短路径的完整表示，然后经过多次迭代，每次增加一个新结点，在允许这个结点作为中间 结点的条件下， 计算每一对顶点间的最短路径的缩短变化， 直到所有结点都可以考虑进去为 止，结果得到第一对顶点间的最短路径。主要计算过程是在关系矩阵上的迭代和修改。 返回布尔值 TRUE 当且仅当图中不包含从源结点可达的负权值回路。 三详细设计： 一般地， 在最短路径问题中， 给出一有向图 G=(V,E)， 以及在其上定义的加权函数 w:ER 路 径 p( K VVV, , 10 )的权是指构成路径的所有边的权值之和，即 k i ii vvwpw 1 1 ),()( 从 U 到 V 之间的最短路径的权值为 没有路径存在到若从 的一条路径到为 VU vuppw vu : :)(min ),( ),()(vupw从结点u到v的最短路径的权值。 )(v：表示的最短路径树中v的的父结点 )(vd：表示从源结点s到v的最短路径权值的上界 G=（V，E）是有向加权图，其中加权函数为REw; S
