重大灾害条件下基于GIS的最短路径改进算法

Shortest path improved algorithm based on GIS under large-scale disaster

利用经典的Dijkstra算法,对重大灾害条件下Dijkstra算法进行了改进,构建了惩罚因子函数,结合GIS软件二次开发模块,通过Visual C++6.0实现了复杂网络的分析功能。分析了重大灾害条件下节点数量对于道路可靠性以及最优路径选取的影响,综合考虑距离、行程时间以及节点数量因素,证明了改进Dijkstra算法对于最优路径选择的优越性。分析结果表明:利用改进Dijkstra算法、经典Dijkstra算法计算出的路径节点数分别为31、59,行程时间基本相同。可见,改进算法能有效减少疏散路径中的节点数量,降低车辆在节点处的延误损失和风险。

The Dijkstra algorithm under large-scale disaster was improved by using classical Dijkstra algorithm,and the function of penalty factor was built.Complex network analysis function was realized by using Visual C＋＋ 6.0 and the secondary development module of GIS.The impacts of node quantity on road reliability and the selection of optimal path under large-scale disaster were analyzed.Distance,travel time and node quantity were considered,the advantage of improved Dijkstra algorithm in the selection of optimal path was proved.Analysis result shows that the node quantities computed by improved Dijkstra algorithm and classical Dijkstra algorithm are 31,59 respectively,travel times are almost same.So the improved algorithm can reduce the node quantity in evacuation route effectively,and decrease the delay loss and risk of vehicle at the node.1 tab,2 figs,11 refs.