通信网最短路径课程设计--基于C语言对D算法最短路径的求解

1、 课程设计说明书 NO.1 基于基于 C C 语言对语言对 D D 算法算法最短路径最短路径的求解的求解 1.1.课程设计的目的课程设计的目的 为了巩固“通信网基础及应用”课程学到的相关知识，通过对本课程所学知识的综 合运用，使学生融会贯通课程中所学的理论知识，初步掌握通信网络的体系结构和扩频 通信系统等相关知识；加深对通信网络的基本理论、基本知识和常用技术的理解；提高 学生分析问题的能力和实践能力，培养科学研究的独立工作能力。 2.2.设计方案论证设计方案论证 2.1 最短路径算法的分类 1966 年 Roth 提出的 D 算法，可以认为是拓扑结构测试中最经典的方法，也是最早 实现自动化的测

2、试生成算法之一。它是完备的测试算法，它可以检测非冗余电路中所有 可以检测的故障。虽然它是在 20 世纪 60 年代提出的，而且被改正过多次，但是，许多 新的测试方法都是在它的基础上发展起来的。而且一直沿用至今。 D 算法在具体应用时，计算工作量很大，尤其是对大型的组合电路计算时间很长, 原因是在作敏化通路的选择时其随意性太大，特别是在考虑多通路敏化时各种组合的情 况太多， 然而真正 “有效” 的选择往往较少， 做了大量的返回操作。 改进的算法， 如 PODEM 和 FAN 算法，有效地减小了返回次数，提高了效率。 在进行通信网选择路由时，首选路由和各个迂回路由通常都是按照路径最短的原则 进行的

3、，目的是为了使网络费用达到最小。在实际中都是由计算机实现这两种算法来帮 助设计人员进行路由设计。 在固定路由选择中，常按照最短路径的原则来确定节点的由表。最短路径有两个算 法，一个是 Dijkstra 算法，是解决一个节点到其它节点之间的最短路径的问题；另一 个是 Floyd 算法，可用来求解网中任意两个节点之间的最短路径。 最常用的路径算法有： 1.Dijkstra 算法,是解决一个节点到其他节点之间的最短路径的问题。 2.Floyd-Warshall 算法，可以用来求解网中任意两个节点之间的最短路径。 所谓最短路径问题是指：已知 G（V，E） ，我们希望找出从某给定的源结点 SV 到 V

4、中的每个结点的最短路径。 我们可以发现有这样一个事实：如果 P 是 G 中从 vs 到 vj 的最短路，vi 是 P 中的 课程设计说明书 NO2 一个点，那么，从 vs 沿 P 到 vi 的路是从 vs 到 vi 的最短路。 2.2 Dijkstra 算法的基本原理 Dijkstra 算法解决的是有向图中最短路径问题。Dijstra 算法的基础操作是边的拓 展。 已知图G=(V,E)，将其节点集分为两组：置定节点集Gp和未置定节点集G-Gp。其中 Gp内的所有置定节点， 是指定点vs到这些节点的路径为最短 （即已完成最短路径的计算） 的节点。而G-Gp内的节点是未置定节点，即vs到未置定节点距离是暂时的，随着算法的 下一步将进行不断调整，使其成为最短径。在调整各未置定节点的最短径时，是将 Gp中的节点作为 转接点。具体地说，就是将 Gp中的节点作为转接点，计算（vs,vj）的径长（vjG-Gp） ，若该次计算 的径长小于上次的值，则更新径长，否则，径长不变。计算后取其中径长最短者