1、课程设计说明书 NO.1 C C 语言语言环境环境下下 D D 算法完成算法完成最短路径最短路径求解求解 1 1. .课程设计的目的课程设计的目的 为了巩固“通信网基础及应用”课程学到的相关知识，通过对本课程所学知识的综 合运用，使学生融会贯通课程中所学的理论知识，初步掌握通信网络的体系结构和扩频 通信系统等相关知识；加深对通信网络的基本理论、基本知识和常用技术的理解；提高 学生分析问题的能力和实践能力，培养科学研究的独立工作能力。 2 2. .设计方案论证设计方案论证 2.12.1 最短路径算法的分类最短路径算法的分类 用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径
2、算法”。 最常用的路径算法有： 1.Dijkstra 算法,是解决一个节点到其他节点之间的最短路径的问题。 2.A*算法。 3.SPFA 算法。 4.Bellman-Ford 算法。 5.Floyd-Warshall 算法，可以用来求解网中任意两个节点之间的最短路径。 6.Johnson 算法。 所谓单源最短路径问题是指：已知 G（V，E） ，我们希望找出从某给定的源 结点 SV 到 V 中的每个结点的最短路径。 首先，我们可以发现有这样一个事实：如果 P 是 G 中从 vs 到 vj 的最短路，vi 是 P 中的一个点，那么，从 vs 沿 P 到 vi 的路是从 vs 到 vi 的最短路。
3、2.22.2 经典经典 DijkstraDijkstra 算法的主要思想算法的主要思想 Dijkstra 算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中 dj是从起 源点 s 到点 j 的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其 长度等于零)； pj则是从 s 到 j 的最短路径中 j 点的前一点。 求解从起源点 s 到点 j 的最 课程设计说明书 NO2 短路径算法的基本过程如下： 第一步：初始化。令 N=1。对于不在 N 中的每个节点 v，设置 D（v）=l（1，v） （对于与 1 不直接相连的节点取为）。 第二步：找到一个不在 N 中的使 D（
4、w）最小的节点 w，并将 w 加进集 N 中去， 然后计算下式，以修改不在 N 中的所有其他节点的 D（v）： D（v）=minD（v），D（w）+l（w，v） 重复第二步，直至全部节点包括在 N 中。 2.32.3 DijkstraDijkstra 算法的实现算法的实现 我们利用图 1 中所示的网作为例子讨论 Dijkstra 算法，我们的目的是求出源节点 到网中所有其他节点的最短路径。 在求解过程中，采取步进方式，建立一个以源节点 1 为根的最短路径树，直到包括 最远的节点在内为止。到第 k 步，计算出到离源节点最近的 k 个节点的最短路径。这些 路径定义为在集 N 内。 图图 1 1 一
5、个网络的例子一个网络的例子 在按标记法实现 Dijkstra 算法的过程中，核心步骤就是从未标记的点中选择一个权值 最小的弧段。要选择一个权值最小的弧段就必须把所有的点都扫描一遍，将这些要扫描 的点按其所在边的权值进行顺序排列，这样即可大大提高算法的执行效率。 课程设计说明书 NO.3 2.4 Dijkstra2.4 Dijkstra 算法的基本原理算法的基本原理 Dijkstra 算法解决的是有向图中最短路径问题。Dijstra 算法的基础操作是边的拓 展。 图 2 中示出了以源节点 1 为根的最短距离树。它的产生过程是：当一个节点加入集 合 N 时，它就连接到已在 N 中的适当点。每个节点
6、下面圆圈内的数字代表在第 n 步该 节点加入树结构。由节点 1 的最短距离树可以得到节点 1 的路由选择表，如图 3 所示。 该表指明了到相应的目的的地节点所应选的下一节点。 同理， 我们可以求得节点 2,3， ， 6 的路由选择表。 图图 2 2 节点节点 1 1 到其他节点的最短距离到其他节点的最短距离（a a） 课程设计说明书 NO.4 目的节点 下一节点 2 2 3 4 4 4 5 4 6 4 图图3 3 节点节点1 1到其他节点的最短距离（到其他节点的最短距离（b b） 2.4.1 Dijkstra 算法的基本过程算法的基本过程 Dijkstra算法是最短路径算法中最典型的一种算法， 求最短路径就是解决一个节点 到其他节点之间的最短路径的问题。 Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用 OPEN, CLOSE表方式。 大概过程： 创建两个表，OP
