• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

关于最短路径的SPFA快速算法

段凡丁

段凡丁. 关于最短路径的SPFA快速算法[J]. 西南交通大学学报, 1994, 7(2): 207-212.
引用本文: 段凡丁. 关于最短路径的SPFA快速算法[J]. 西南交通大学学报, 1994, 7(2): 207-212.

关于最短路径的SPFA快速算法

  • 摘要: 本文提出了关于最短路径问题的一种新的快速算法─—SPFA(ShortestPathFasterAlgorithm)算法.SPFA算法采用动态优化逼近的方法,用邻接表作为有向图的存储结构,用了一个先进先出的队列Queue来作为待优化点的存储池。算法的时间复杂性为O(e),在绝大多数情况下,图的边数e和顶点数n的关系是e<n ̄2,因此,SPFA算法比经典的Dijkstra算法在时间复杂性方面更优越。

     

  • 加载中
计量
  • 文章访问数:  1486
  • HTML全文浏览量:  61
  • PDF下载量:  117
  • 被引次数: 0
出版历程
  • 刊出日期:  1994-04-25

目录

    /

    返回文章
    返回