基于半边数据结构的最短路径算法及其实现

Halfedge data structure based shortest path algorithm

在分析传统最短路径算法数据结构的基础上,提出并实现了一种以半边数据结构存储网络拓扑数据的最短路径算法。该算法充分利用半边数据结构存储格式紧凑、操作直观高效等方面的优点,采用较传统方法不同的路径检索方式,实现了快速计算网络中任一结点到其他所有结点的最短路径。实验表明,基于半边数据结构的最短路径算法可以大幅度提高网络中最短路径的计算效率,其性能在网络结点显著增多时愈加明显。

In this paper,a novel shortest path algorithm based on the famous half-edge structure is introduced.In light of efficient data accessing of half-edge structure,a different strategy of shortest path searching is used.The algorithm has ability of calculating the shortest paths from an arbitrary given node to the other nodes in network.Experiments and results show that the algorithm can perform more efficiently than traditional ways,especially when the calculated network is a large scale and sparse one.