栅格数据中附有条件的最短路径算法.docVIP

栅格数据模型中附有条件的最短路径算法 厍向阳1，史经俭2，罗晓霞1 1（西安科技大学计算机科学与技术系，陕西 西安 710054） 2（西安科技大学测量工程系，陕西 西安 710054） 1(xiangyangshe@) 摘(要:为了研究栅格数据模型中附有条件的最短路径算法，将附有条件最短路径概括为：（1）点约束的最短路径问题；（2）边约束的最短路径问题；（3）属性约束的最短路径问题问题。以栅格数据模型为图或网络描述方式，基于贪心算法思想，提出栅格数据模型中附有条件的最短路径算法。最后，通过实例进行了算法测试和比较。算法测试表明：栅格数据模型中附有条件的最短路径算法是完全可行和有效地。 关 键 词：栅格数据；最短路径；点约束；边约束；属性约束 中图分类号:TP393.3 文献标识码shortest path algorithm confined in conditions in grid data model Shexiangyang1 Shijingjian2 Luoxiaoxia1 1（Department of Computer Science and Technology; Xi’an University of Science and Technology; Xi’an 710054）（Department of and Mapping; Xi’an University of Science and Technology; Xi’an 710054）Abstract: To study the shortest path algorithm confined in conditions in grid data model,the shortest path question confined in conditions is generalized :(1) the shortest path question confined in point set; (2) the shortest path question confined in edge set; (3) the shortest path question confined in attribute set, in view of practice demand. The shortest path algorithm confined in conditions in grid data mode is put forward, expressing graphic or network by grid data model, based on greedy idea. In the end, the algorithm is validated and compared by examples. Algorithm testing show: the shortest path algorithm confined in conditions in grid data model is completely feasible and availability. Key words: grid data; shortest path; point set constraint; edge set constraint; attribute set constraint 引言 最短路径算法按照数据模型，可分为基于栅格数据模型和基于矢量数据模型两种。基于矢量的最短路径算法沿着具体的路线和结点，找出一条距离最短或时间最短或成本最小的路径，该路径是原有矢量图中多个弧段的组合，主要应用于交通路线的选择等。基于栅格模型的最短路径算法使用栅格数据（图像数据、Arc/info的GRID数据等）模型描述图或网络，采用适当的数据结构存储数据，在此基础上使用一定的算法找出一条最短路径，它主要应用于大范围的区域分析，如森林大火的传播路径分析、疾病的传播路径分析、文化的传播分析、救灾线路选择及道路工程设计等。当前最短路径算法研究绝大部分是基于矢量数据模型的，发展相对较为成熟[1][2][3][4][5][6]，而基于栅格数据模型的最短路径算法仅有少量研究成果或仅仅提出这一设想[7][8][9]，在目前地理信息系统软件中，最短路径分析大部分是基于矢量数据模型的。随着科学研究的深入和生产实际的发展，最短路径算法面临新的问题。例如：在物流配送中，往往要求车辆由中心仓库向数个配送点送货，最后到达目的地，这种情况下的最短路径如何求解。同样，在运送危险物品或银行运送钞票时，要求回避一些点、边或某一路径，这种情况下的最短路径如何