中文会议： 计算机科学

会议日期： 2004-10-22

会议地点： 武汉

主办单位： 中国计算机学会

作　　者： ; ; ;

机构地区： 中山大学信息科学与技术学院计算机科学系

出　　处： 《2004年全国理论计算机科学学术年会》

摘　　要： 最短路径问题一直是计算机科学、地理信息学、交通工程学等学科的一个研究热点.在关于最短路径算法的各种研究中,能取得比经典Dijkstra算法好的结果却很少.在Dijkstra算法以后提出的很多最短路径算法研究文献都愿意与Dijkstra算法进行对比,本文也不例外.Dijkstra算法复杂度为O(n2).通过扩展编码路径视图结构,给出了一个支持最短路径查询的层次模型,但在算法中需要进行一定的预先计算,所以当图被修改时,还需要重新计算,当图中节点很多时,尚需要相当长时间.通过预先计算"组成分层"的结构以达到提高查找最短路径的效率,并与Dijkstra算法进行了比较,但该算法在某些类型的图中其效率没有Dijkstra算法好,且同样存在当图发生改变时需要重新计算的问题.

关 键 词： 空间位置 最短路径算法 算法

领　　域： [自动化与计算机技术]