通信网理论基础实验指导书 吉林大学通信工程学院通信网课程组 2008 年 5 月 目 录 实验一:路径选择实验 ................................ 1 实验二:通信业务量分析实验 .......................... 4 实验三:Gompertz(龚伯兹)模型实验 .................... 8 实验四:Logistic(罗吉特)模型实验 ................... 13 1 实验一:路径选择实验 一、实验目的 在进行通信网选择路由时,首选路由和各个迂回路由通常都是按照路径最短的原则进行的,目的是为了使网络费用达到最小。在求解最短径的算法中常用的有 D 算法和 F算法。D 算法用于求指定节点到其他各节点的最短路径;F算法用于求任意端间最短径。在实际中都是由计算机实现这两种算法来帮助设计人员进行路由设计。本次实验目的就是要使学生深入理解这两种算法并能用计算机实现这两种算法。 二、实验内容 1.用编程语言实现 D 算法。 2.用编程员实现 F算法。 三、实验原理 (一)D 算法 1.D 算法原理 已知图G=(V,E),将其节点集分为两组:置定节点集Gp 和未置定节点集G-Gp。其中 Gp 内的所有置定节点,是指定点 vs 到这些节点的路径为最短(即已完成最短路径的计算)的节点。而 G-Gp 内的节点是未置定节点,即 vs 到未置定节点距离是暂时的,随着算法的下一步将进行不断调整,使其成为最短径。在调整各未置定节点的最短径时,是将 Gp 中的节点作为转接点。具体地说,就是将 Gp 中的节点作为转接点,计算(vs,vj)的径长(vj∈G-Gp),若该次计算的径长小于上次的值,则更新径长,否则,径长不变。计算后取其中径长最短者,之后将 vj 划归到 Gp 中。当(G-Gp)最终成为空集,同时 Gp=G,即求得 vs 到所有其他节点的最短路径。 jw :表示 vs 与其他节点的距离。 在 Gp 中,w i 表示上一次划分到 Gp 中的节点 vi 到 vs 的最短路径。 在 G-Gp 中,表示从 vs 到 vj )(pjGGv仅经过 Gp 中的节点作为转接点所求2 得的该次的最短路径的长度。 如果vs 与vj 不直接相连,且无置定节点作为转接点,则令jw。 2.D 算法实现流程 D 算法流程如图1 所示。 在G-Gp中找到点vj,使vs到点vj的距离最小,并将vj划归到Gp以新Gp中的节点作为转接点,计算并修改(G-Gp)中的w j 将vi划归到Gp中,即新的 iv,svG p ,sidiwvj与vs直连且未置定节点标值ijj =dwGp ={vs} w s=...