基于节点合并的最短路问题新算法  

New Algorithm for Shortest Paths Based on Node Combination

作　　者：吕欣[1] 李勇[1] 邓宏钟[1] 谭跃进[1] 

机构地区：[1]国防科技大学信息系统与管理学院,湖南长沙410073

出　　处：《小型微型计算机系统》2009年第4期695-699,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(70501032;70771111)资助

摘　　要：提出一个解决非负权网络最短路问题的节点合并算法.该算法以将距离起始节点最近的邻居节点拉到身边的方法,与距离最近节点不断合并,重复这一动作,最终求得起始节点到其他节点的最短路距离.与Dijkstra算法相比,节点合并算法不存在节点着色操作,始终只考虑起始节点的邻居,实现步骤更加简单,整个过程可以采用向量化操作,易于理解和编程实现.数据试验表明,节点合并算法求解效率明显高于Dijkstra算法.This paper proposes a Node Combination algorithm for the Shortest-Path of real-weighted networks. By the method of dragging the start node＇s nearest neighbor to itself, it combines the nearest node repeatedly, and finally gains the lengths of the shortest paths between the start node and all other nodes. Compared with the Dijkstra algorithm, it is a new algorithm without node labeling operations, it takes no but the start node＇s neighbors into account all the time. While the whole process could be manipulated with vectors, it is more comprehensible and convenient for programming. With the experimental evaluation on a variety of networks, it shows that it gains more computing efficiency than Dijkstra.

关 键 词：最短路 节点合并 节点合并算法Dijkstra算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]