科研之友
微信
新浪微博
Facebook
分享链接
摘要
最短径路是网络优化中的一个经典问题,Dijkstra算法被公认为是一种十分有效的最短径路的搜索求解算法.本文在研究网络一般结构特点的基础上,发现传统Dijkstra算法在每次迭代过程中都需要搜索所有节点的这一缺陷,通过向搜索节点中引入“度”的信息,提出了基于“度搜索”的改进算法,并根据网络的特点,给出了有向网络和无向网络两种情况下存在“度”差异的算法设计方法;算法的整体结构与Dijkstra保持了一致性,没有算法结构的突变,因而通过修改原有Dijkstra程序和重新设计“度搜索”程序都十分容易实现.该算法提高了最短径路的搜索效率,特别是对稀疏网络,算法效率更为明显,其复杂度小于O(|V|2).
- 单位
