计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (8): 118-120.DOI: 10.3778/j.issn.1002-8331.2009.08.035
王继东1,2,陈桂林1
WANG Ji-dong1,2,CHEN Gui-lin1
摘要: 在分析传统最短路径算法数据结构的基础上,提出并实现了一种以半边数据结构存储网络拓扑数据的最短路径算法。该算法充分利用半边数据结构存储格式紧凑、操作直观高效等方面的优点,采用较传统方法不同的路径检索方式,实现了快速计算网络中任一结点到其他所有结点的最短路径。实验表明,基于半边数据结构的最短路径算法可以大幅度提高网络中最短路径的计算效率,其性能在网络结点显著增多时愈加明显。