数据结构课程设计图点间最短路径算法.docVIP

数据结构课程设计 设计题目：图顶点间最短路径算法 专 业：计算机科学与技术 班 级：2006050304 姓 名： 学 号：200605030411 指 导 老 师： 完 成 时 间：2009-5-9 一：需求分析： 问题描述：路径问题在图论中占有重要位置，因为这与日常生活中的许多问题有着广泛的联系。比如乘汽车旅行时，我们总希望找出到目的地尽可能短的线路；如果在地图上标出每两个路口之间的距离，如何找出一条最短的行车路线？在这个例子中我们可以把地图模型化为一个图，结点表示一段公路的起点和终点，边的权值表示公路的长度。我们的目标是从起点出发找出一条到达目的地的最短路径。一种直接的方法就是列举出所有的路径，并计算出每条路径的长度，然后选择最短的一条。容易看出，即使不考虑包含回路的路径，在起点和终点之间依然可能存在很多不同的行车路线，而其中绝大多数是不必考虑的。 二：概要设计 设计思想： Ⅰ Dijkstra算法的基本思想： 这种算法是解决有向图的最短路径问题的条件是该图所有边的权值是非负值。Dijkstra 算法定义了一结点集合，从源结点到集合是任一点的最短路径的权值均已确定。算法反复地从集合中挑选出其最短路径估计为最小的结点，并将最小结点插入集合，并对和最小结点相邻的所有边进行松弛。 Ⅱ Bellman-ford算法的基本思想： Floyd能在边的权值为负的情况下解决单源最短路径问题。已知有向加权图G=（V，E），设其源结点为S，加权函数w：E→R，对该图运行FLOYD算法可返回一布尔值，表有图中是否存在一个从源结点可达的权值为负的回路。如果存在这样的回路，则算法返回FLASE，说明该问题无解。若不存在这样的回路，算法将产生最短路径及其权值Floyd算法运用了松弛技术， 对每一个结点并逐步减小从源到的最短路径的权值的估计值直至达到实际的最短路径. Ⅲ Floyd算法基本思想： 设带权图G=(V,E)，有N个顶点，图采用邻接矩阵作为存储结构。Floyd算法是以关系矩阵为基础，把关系矩阵看成是没有经过任何中间结点，直接可以到达的每一对顶点间的最短路径的完整表示，然后经过多次迭代，每次增加一个新结点，在允许这个结点作为中间结点的条件下，计算每一对顶点间的最短路径的缩短变化，直到所有结点都可以考虑进去为止，结果得到第一对顶点间的最短路径。主要计算过程是在关系矩阵上的迭代和修改。 返回布尔值TRUE当且仅当图中不包含从源结点可达的负权值回路。 三详细设计： 一般地，在最短路径问题中，给出一有向图G=(V,E)，以及在其上定义的加权函数w:E→R 路径p()的权是指构成路径的所有边的权值之和，即 从U到V之间的最短路径的权值为 从结点到的最短路径的权值。 ：表示的最短路径树中的的父结点 ：表示从源结点到的最短路径权值的上界 G=（V，E）是有向加权图，其中加权函数为 S为源结点 通过下面的算法对进行初始化： INITIALIZE-SINGLE-SOURCE(G,s) { for (每一个结点) { ； ；} ； } 经初始化以后，对所有的，有；对-{s}，有且。采用松弛技术去松弛一条边的过程包括测试是否可能通过结点对迄今找出从S到V的最短路径进行改进。如果可能，则更新和。一次松弛操作可以减小最短路径估计值并更新的祖先域，下面过程实现对边进行一次松弛操作。 RELAX { if (+) { =+; =u; } } Dijkstra 算法描述： 输入：G=(V,E),加权函数w,源结点s 输出：从源s到v的最短路径 Algorithm DIJKSTRA (G,W,S) { Initialize-single-source(G,s) S=； Q=V[G]； while(Q!= )do {u=extraqct-min(Q); S=S; for(每一个结点vAdj[u]) RELAX; } } Bellman-Ford 算法描述： 输入：G=(V,E),加权函数w,源结点s 输出：从源s到v的最短路径 Algorithm BELLMAN-FORD (G,W,S) {Initialize-single-source(G,s); For(i=1 to |V[G]|-1) for(每一条边（u,v）E[G]) RELAX; for(每一条边（u,v）E[G]) if(+) return false; return true; } Floyd算法描述： void Floyd(){ int i,j,k; for(k=1;k=n;k++) for(i=1;i=n;i++) for(j=1;j