基于Dijkstra算法的多约束军事运输最优路径研究

Study on Optimal Path for Multiple-Constraint Military Transportation Based on Dijkstra Algorithm

传统Dijkstra算法按照路径长度递增次序产生最优路径,是一种基于单一权值的路径算法。结合军事运输路径规划需要,综合考虑路径长度、道路等级、安全性等多种约束条件,对传统Dijkstra算法进行拓展,实现多约束条件下的路径选优,并通过限制矩形搜索区域、降低路网规模、减少遍历节点数量提高算法执行效率。

Traditional Dijkstra algorithm usually obtains the optimal path in accordance with the ascending order of path lengths. It is based on a single weight value. Combining the needs of military transportation path planning, taking into con- sideration of multiple constraints of distance, road grade and security, the paper expands the traditional Dijkstra algorithm to obtain the optimal path under multiple-constraint condition. And by limiting a rectangular search area, it narrows road network scale, reduces the number of nodes, and improves the efficiency of the algorithm.