1、课程设计说明书课程设计说明书 NO.1 A*A*最短路径算法的改进最短路径算法的改进 1.1.课程设计的目的课程设计的目的 本课程设计是学习数据通信与通信网技术课程必要的教学环节。由于该课程是 专业必修课，需要通过实践巩固基础知识，为使学生取得最现代化的设计技能和研究方 法，课程设计训练也就成为了一个重要的教学环节。通过对路由算法的设计和实现，达 到进一步完善对通信网基础及应用课程学习的效果。 2.2.设计方案论证设计方案论证 算法具体的形式包括： 确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最 短路径的问题
2、。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同 于把所有路径方向反转的确定起点的问题。 确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题：求图中所有的最短路径。 （1）Floyd 求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度 O(V3)。 Floyd-Warshall 算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径 的一种算法，可以正确处理有向图或负权的最短路径问题。 Floyd-Warshall 算法的时间复杂度为 O(N3)，空间复杂度为 O(N2)。 Floyd-Warshal
3、l 的原理是动态规划： 设 Di,j,k 为从 i 到 j 的只以(1k)集合中的节点为中间节点的最短路径的长度。 若最短路径经过点 k，则 Di,j,k = Di,k,k-1 + Dk,j,k-1； 若最短路径不经过点 k，则 Di,j,k = Di,j,k-1。 因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。 在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至 二维。 沈 阳 大 学 课程设计说明书课程设计说明书 NO2 Floyd-Warshall 算法的描述如下： for k 1 to n do for i 1 t
4、o n do for j 1 to n do if (Di,k + Dk,j O（E*lgV）。 当是稀疏图的情况时，此时 E=V*V/lgV，所以算法的时间复杂度可为 O（V2） 。 若是斐波那契堆作优先队列的话，算法时间复杂度，则为 O（V*lgV + E）。 （3）Bellman-Ford 求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好， 时间复杂度 O（VE）。 Bellman-Ford 算法是求解单源最短路径问题的一种算法。 单源点的最短路径问题是指：给定一个加权有向图 G 和源点 s，对于图 G 中的任意 一点 v，求从 s 到 v 的最短路径。与 Dijkstra 算法不同的是，在 Bellman-Ford 算法中， 边的权值可以为负数。设想从我们可以从图中找到一个环路（即从 v 出发，经过若干个 点之后又回到 v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任 意两点的最短路径就可以无穷小下去。 如果不处理这个负环路， 程序就会永远运
