网络最短路径的动态算法  

A New Dynamic Algorithms for Network Minimun Distance

作　　者：安红岩[1] 胡光岷[2] 何永富[1] 

机构地区：[1]成都理工大学应用数学系,成都610059 [2]电子科技大学宽带光纤传输与通信系统技术国家重点实验室,成都610054

出　　处：《计算机工程与应用》2003年第1期173-174,180,共3页Computer Engineering and Applications

摘　　要：在通信网络中,两个节点间最短路径的计算是大多数路由算法的基础,对整个网络的性能有重要的影响。该文针对动态变化的网络环境,提出了一种快速的动态最短路径树算法(DMDT),并给出了算法的实现步骤。随机网络模型的仿真结果表明:DMDT算法生成的最短路径树与Dijstra算法基本一致,计算的时间复杂度较Dijstra算法有很大降低。为动态最短路径树的计算提供了一种新的选择。The Computing of the minimum distance between two nodes in the communication network is the basis of almost all the routing arithmetic.It has important influences on the character of the whole network environment ,the paper puts forward a fast arithmetic to the Dynamic Minimum Distance Tree(DMDT)and gives the process which makes the arithmetic into fact.Simulations results of the imitated model of the random network show that the minimum distance tree by the DMDT is almost the same as that by Dijstra and the complex degree of time has much more decreased than the Dijstra.In one word,DMDT is a new choice for the dynamic minimum tree.

关 键 词：网络最短路径 动态算法 通信网络 随机网络模型 

分 类 号：TN915[电子电信—通信与信息系统]