The Improvement and Implementation of the Network Shortest Path Algorithm

从节约存储空间和提高运算速度方面对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.福建省自然科学基金(D0310001)资