• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus
  • Indexed by Core Journals of China, Chinese S&T Journal Citation Reports
  • Chinese S&T Journal Citation Reports
  • Chinese Science Citation Database
Volume 17 Issue 5
Oct.  2004
Turn off MathJax
Article Contents
LI Yin-zhen, GUO Yao-huang. Bound Searching Algorithm for Shortest Path in a Network[J]. Journal of Southwest Jiaotong University, 2004, 17(5): 561-564.
Citation: LI Yin-zhen, GUO Yao-huang. Bound Searching Algorithm for Shortest Path in a Network[J]. Journal of Southwest Jiaotong University, 2004, 17(5): 561-564.

Bound Searching Algorithm for Shortest Path in a Network

  • Publish Date: 25 Oct 2004
  • Many irrelevant vertexes must be searched in order to find the shortest path between two vertexes in a large networkwith Dijkstra algorithm, resulting in low efficiency. To improve the searching efficiency, a new searching algorithm, named bidirectional bound searching algorithm, was proposed. With this method, a shortest path from the source vertex to the terminal vertex via any vertex is determined first by bidirectional searching. This path is closed to or even the same as the shortest path to be found. The length ofthis path is then taken as a bound, and any vertex with larger label value than the bound in later calculations will not be considered. Itwas proved that the calculating efficiency of the newalgorithmwas as twice as that of the traditional Dijkstra algorithm

     

  • loading
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Article views(1721) PDF downloads(184) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return