双向半序网在两点间最优路径算法中的应用  

Application of Bidirectional Semi-order Net in Best Path of Two Nodes

作　　者：刘立嘉[1,2] 盛业华[1] 路明月[1] 陈旻[1] 黄云[1] 

机构地区：[1]南京师范大学虚拟地理环境教育部重点实验室,南京210046 [2]石家庄铁道学院计算机系,石家庄050043

出　　处：《计算机工程》2008年第7期73-75,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(40671147)

摘　　要：最优路径搜索是地理信息系统重要的网络分析功能,也是其他网络分析功能的基础。该文在分析最优路径算法的基础上,针对特定两点间的最优路径问题,提出一种双向最优半序网结构,通过双向搜索构建该种双向最优半序网,可快速解得指定两点间所有满足最优条件的路径,并给出相应算法。结合计算实例分析并评价了该算法的运行效率。In geographic information system, the best path searching is the basis of other network analysis. Based on the research results in the field of the best path, this paper puts forward an efficient best path searching algorithm based on bidirectional semi-order net to solve the best path searching of two assigned nodes. And this algorithm is evaluated for its practical efficiency with several computing examples. The application prospect and advance of the algorithm are discussed.

关 键 词：网络分析 最优路径 最短路径 双向半序网 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]