网络最短路径算法的改进及实现  

The Improvement and Implementation of the Network Shortest Path Algorithm

作　　者：李峰[1] 张建中[1] 

机构地区：[1]厦门大学通信工程系,福建厦门361005

出　　处：《厦门大学学报（自然科学版）》2005年第B06期236-238,共3页Journal of Xiamen University：Natural Science

基　　金：福建省自然科学基金(D0310001)资助

摘　　要：从节约存储空间和提高运算速度方面对Dijkstra最短路径算法进行了改进.定义新的节点类来高效存储网络的拓扑信息,节省了计算机存储空间;采用满二叉堆数据结构对节点进行排序并选取最短路径节点,大大提高算法效率.仿真例子表明,对于某些网络结构,改进算法能把传统Dijkstra算法的时间复杂度由原来的O(N2)近似降至O(N).From economizing memory space and increasing operation speed,The Dijkstra Algorithm analysis efficiency was improved by using a new node class to store the topological information of the network.The data structure of full binary heap are used to get the shortest path value node and in which the new nodes are inserted in a queue.The emulational result proves that in some network structures,the complexity of the calculation time can be reduced from o(N2) to nearly o(N) by improved algorithm.

关 键 词：最短路径算法 DIJKSTRA算法 存储空间 时间复杂度 拓扑信息 存储网络 运算速度 数据结构 算法效率 改进算法 网络结构 节点 计算机 仿真 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O157.5[自动化与计算机技术—计算机科学与技术]