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

被引：14

作者：

李峰

张建中

机构：

[1] 厦门大学通信工程系

[2] 厦门大学通信工程系福建厦门361005

来源：

厦门大学学报(自然科学版) | 2005年 / S1期

关键词：

Dijkstra算法; 邻接节点数组; 堆排序;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

从节约存储空间和提高运算速度方面对Dijkstra最短路径算法进行了改进.定义新的节点类来高效存储网络的拓扑信息,节省了计算机存储空间;采用满二叉堆数据结构对节点进行排序并选取最短路径节点,大大提高算法效率.仿真例子表明,对于某些网络结构,改进算法能把传统Dijkstra算法的时间复杂度由原来的O(N2)近似降至O(N).

引用

页码：236 / 238

页数：3

共 6 条

[1] 低代价最短路径树的快速算法 [J].