基于改进的Dijkstra算法躲避卫星侦查的路线选择
章胤 李瑞敏 郝茂林 王嘉瑜 孙鹏越 高琪
摘 要：由于卫星在军事领域的应用，卫星侦察下的军事运输路线选择得到广泛关注。本文通过分析卫星在其星下点的轨迹，并生成道路缓冲区，借助地理信息系统（GIS）和改进的Dijkstra算法，为卫星侦察下的最优路径选择提供了更优途径。将该方法应用于实际问题中，程序运行所用时间为7.44秒，而经典Dijkstra算法运行时间为16.83秒，改进后的Dijkstra算法相比经典算法节约了近10秒，一定程度上能使相关最优选择问题的效率得到提高。
关键词：卫星运动；公路运输；路线选择；GIS；Dijkstra算法
中图分类号：TP301.6 文獻标识码：A
1 引言（Introduction）
随着空间军事化的高速发展，卫星侦察因其可以获得全天候、大范围、近实时的战场信息，被认为是从外层空间采集地理信息的强有力的手段。为了保护国家机密，在军事运输过程中必须要躲避航天卫星的侦察并要在规定时间内尽快到达目的地。因此，快速生成安全的最短运输路线，躲避卫星侦查，实现安全运输显得尤为重要。
国内外对军事运输路线选择的研讨处于发展完善阶段。Rui Neves-Silva等人提出利用扩展的Dijkstra算法计算灾害中撤离人员的替代路线[1]。Akshay Kumar Guruji等人利用在碰撞阶段之前确定启发式函数的值来代替初始化的一种路径规划算法，以寻找机器人工作时的无碰撞路径，该算法减少了问题处理时间[2]。Xiu Li Gao等人研究改进的Dijkstra算法解决动态路径选择问题[3]。在国内，王辉等人提出利用Dijkstra算法和改进的蚁群算法解决泊车系统的路径规划问题[4]。沈睿等人使用GIS数据模型和改进的Dijkstra算法，缩短了智能交通系统寻求最短路径的搜索时间[5]。姚志敏提出了将Dijkstra算法总计算步数由原来的步减少为不到步的方法[6]。
本文结合卫星的运行轨迹和覆盖范围，以经典Dijkstra算法为基础，对算法进行一定的改进，提高了在卫星影响下躲避卫星侦察的最优公路运输路线选择的效率和准确性，并借助GIS系统进行模拟。
2 基于Dijkstra算法的路径选择模型（The path
selection model based on Dijkstra algorithm）
2.1 地理信息系统
地理信息系统（Geographic Information System，GIS）是用于不同层次的规划、管理与决策所需要的信息粒度与空间信息的图像表达（可视化）。GIS起源于专题地图，但又高于专题制图。在数字环境下，地图信息成为GIS的基础信息与专题信息的载体，一方面是为了通过图形信息压缩来保证地图的可读性，而更重要的是还负担着生成GIS多尺度数据库的新使命。对于以道路网为代表的人工线状物体集合，利用赋权图原理和结点度的信息使其结构化，进而对其进行全局性评价[7]。在地理信息系统中，道路交叉点和道路分别构成道路交通网络中的点集合和边集合。其中，通过收集点矢量要素和边矢量要素的属性字段，来创建边和点之间的权重属性。如道路的长度、道路的类型、道路的宽度等都可以转换为道路权重。该模型以对道路复杂性适应度高的Dijkstra算法为基础。
2.2 卫星轨道和星下点轨迹
卫星轨道是卫星在获得某一初始水平速度后，可以环绕地球飞行的运行轨迹。根据开普勒第一定律，卫星运转轨道的平面，是一个以地心为其中的一个焦点的椭圆。决定卫星运行轨道的参数主要有六种[8]，分别是长轴a、偏心率e、轨道倾角i、升交点赤经、近地点幅角和过近地点时刻t。卫星的星下点是指卫星和地心的连线与地面的交点。星下点轨迹是因卫星运动与地球的自转使得星下点在地球表面进行移动所形成的轨迹。由于地球自转，卫星星下点轨迹的前一圈与后一圈一般不重合。当考虑地球自转时，卫星的星下点轨迹计算公式[9]为：
上述公式中：表示地心纬度、表示地心经度、表示卫星平均角速度、i表示轨道倾角、表示卫星升交点相对经度零点的西退速率、表示卫星经过升交点时的经度、表示卫星经过升交点以后经历的时间。
2.3 卫星覆盖范围
以卫星在当前时刻下，在地面上所有能观察到卫星的点的集合，作为卫星的地面覆盖区域。从理论上来说，如图1所示，卫星到地球表面的两条切线、之间的部分便是卫星的地面覆盖区域。但由于最小观察角的因素，实际的卫星覆盖规模会稍有缩小（即图1中、以内的位置）。同该区域，也就是以卫星 在当前时刻下，所要研究的缓冲区（对应的星下点 为中心，以所对应弧长为半径的地面区域）。在实际地理应用中，将地球视为圆球，单颗卫星的覆盖范围视为是以星下点轨迹为中心，宽度为的条形域。
2.4 影响因素简化
影响运输因素有很多，例如运载工具的种类、道路的交通状况（如红绿灯个数、堵塞程度）、道路上的障碍（如壕沟、涵洞和桥梁）、部队行驶时的指挥人员和驾驶人员的技能，以及当时的气象条件等都是影响军事运输的因素。本文对上述因素不予考虑，仅考虑卫星侦察对道路选择的影响。仅考虑高速公路、县道、省道和国道这四种类型的道路。
2.5 经典Dijkstra算法的主要原理
经典Dijkstra算法是一种通过比较再添加的模型，也称双标记法[10]。并且该算法只适用于边权重均非负的赋权图。对于图，其中V表示顶点集，E表示边集，W表示权集。对图G中的每一点进行标号，其中是从源点s开始到第i个节点的最短路径长度，是第i个节点的直接前趋。其基本思路如下：
（1）对参数进行初始化。令，并标记s点。其他为，均为空。
（2）对于任意未标记的节点j，求。其中表示已标记的节点k到源点s的距离，表示从节点k到节点j的距离。
（3）标记i节点，使得，并取。
（4）重复（2）（3）步，直到所有点的已标记，算法运行完毕。
2.6 Dijkstra算法理解与改进
从2.3中的算法过程中可以看出，每个节点要标记，需要比较其所连接的所有边的最小值，并且最终要标记所有的节点，算法才可以结束。也就是说，对于一张图来说，图中的节点越多，运行算法的时间越长。而对于实际道路中，因地理因素的影响，两地之间的最短距离，往往不包括以两点距离为直径的圆以外的点，并且对于图中边的权值与实际道路长度成正相关，即对于所考虑节点距离较远的节点，显然没必要考虑。所以对于算法遍历的点的数量，可以选择性遍历，在以源点与所求节点欧氏距离为直径的圆内遍历，可进一步减少了循环比较的次数，从而提高算法的运行效率。
在Dijkstra算法运行步骤（2）中，对于遍历所有未标记的节点，传统的Dijkstra算法关于节点的遍历是无序的。我们知道算法要对所有点遍历是不可避免的，但如果图中节点有些权值明显大于其他权值而又要先遍历，到某个节点的最短路径加经过该节点边的直接距离之和中取最小值，在进行最小值判断的时候，权值较大的边会在循环中比较多次，这会制约算法的效率。如果在计算机运行前得到权值的排序，利用这样的排序可以将权值较小的优先比较，那么在与其他边比较的过程中，可以直接舍去一些权值较大的边，从而可以提高算法效率。
引入顺序数组，对节点数据结构加入筛选属性scr，改进的Dijkstra算法的主要思路如下：
（1）初始化源点数据，记scr值为0。对所有边的权重汇总升序编号存入数组中。
（2）在以出发点到汇点为直径的圆，将覆盖到的点。
（3）对圆中未标记的节点j，依数组D的次序，求。其中表示已标记的节点k到源点s的距离，表示从节点k到节点j的距离。
（4）标记i节点，使得，并取。
（5）重复（2）（3）（4）步，直到全部点的已标记，算法运行完毕。
对于增加的卫星过顶因素，以卫星过顶时的缓冲区为参考，一方面减少了所遍历的点的个数，但另一方面会阻碍原始最短路径的选择，并且缓冲区会随着时间规律性移动。
为了解决这些问题，将卫星过顶的缓冲区等效为车辆沿原始最短路行驶下的缓冲区，将经过缓冲区以后的路段进行二次处理。以重新进入缓冲区的节点作为新的源点，重新寻找最短路径，每找到一个中间点，将该点作为新的源点，再次重新寻找最短路径，直到离开卫星缓冲区。
3 应用与实现（Application and implementation）
在Arcgis 10.2，Orbitron 3.71等软件中对算法进行实现。利用Orbitron 3.71获取卫星信息，利用Arcgis 10.2获取地理地图并对其数据库进行处理，利用Arcgis 10.2中自带的Python 2.7脚本实现算法。
3.1 卫星过顶轨迹
选择恰当的卫星，使其星下点轨迹经过所研究的道路。由于卫星不断运动，故设置每1分钟更新一次卫星位置，如图3所示。通过卫星各项参数，计算出卫星扫描范围，生成缓冲区。
3.2 最短路径生成
考虑所选卫星经过的地理区域进行试验，利用Arcgis 10.2绘制河北省秦皇岛市—唐山市地图，地籍数据采集1：10000；经过计算，共得到4597个道路交叉点。假设高速公路行驶时速为匀速100公里/小时，普通公路行驶时速为匀速50公里/小时，不考虑行驶过程中的加、减速时间；假设卫星的覆盖面带是以星下点轨迹为中心，宽度为固定值的条带；假设A地和B地之间有多条路相连，在运输过程中如果按未考虑卫星影响因素生成的最短路径在卫星的覆盖范围内，那么依据卫星所在位置和覆盖范围在卫星覆盖区域外寻找路径或者原地等待。如果经过区域没有被卫星覆盖，那么依照原路行驶；不考虑车队长度对避开卫星的影响。
若采用经典Dijkstra算法脚本运行，因经过缓冲区以后，缓冲区之内的点再次加入，节点最短路径得到更新，所以最终得到的路径并不是在缓冲区影响下的最短路径。采用改进的方法，所生成的道路并不是起点到终点的最短路，而是最短路的近似。其原因在于缓冲区是动态移动的，如按原始选择的道路行驶将会与缓冲区相遇。于是选择更换道路，在卫星无法侦察到的其余道路中选择最短路。
选择以河北省秦皇岛市（119.714°E，39.946°N）为起点，以唐山市（118.172°E，39.615°N）为终点，经过G1高速，杨柏路，再到唐古路，最终到达目的地，途中紅色标线即为躲避卫星侦察的最短路径。通过对比发现，利用改进后的算法，根据卫星进入的时刻，重新记录新起点，程序运行所用时间为7.44秒，而经典算法所运行时间为16.83秒，相比经典算法节约了近10秒，一定程度上缩短了路径选择时间。
4 结论（Conclusion）
本文基于卫星星下点轨迹、卫星覆盖范围和Dijkstra算法的特点，并借助地理信息系统，建立了基于改进的Dijkstra算法躲避卫星侦察的路线选择模型，并通过软件进行了实现，满足了军事运输过程中对隐蔽性和快速性的要求。但本文在对道路进行选择时，仅考虑了常见的道路类型。算法效率虽然得到提高，但也减少了道路选择，使得所求得的距离与实际最短路仍有差距。同时，由于道路限制等其他复杂原因，无法求得真正意义上的最短路径，只能最大程度的接近，也是接下来进一步研究的重点。
参考文献（References）
[1] Rui Neves-Silva，George A.Tshirintzis，Vladimir Uskov，et al.An Extended Dijkstra's Algorithm for Calculating Alternative Routes for Evacuee Agents in Disaster Simulation[J].Frontiers in Artificial Intelligence and Applications，2014：262.
[2] Akshay Kumar Guruji，Himansh Agarwal，D.K.Parsediya.Time-efficient A*Algorithm for Robot Path Planning[J].Procedia Technology，2016：23.
[3] Xiu Li Gao，Tian Jun Hu，Jia Zheng.Research on Dynamic Path Selection Improved Dijkstra Algorithm[J].Advanced Materials Research，2014（1006）：3382.
[4] 王辉，朱龙彪，王景良，等.基于Dijkstra-蚁群算法的泊车系统路径规划研究[J].工程设计学报，2016，23（05）：489-496.
[5] 沈睿，朱学君.基于GIS的最優路径选择的设计与实现[J].工业仪表与自动化装置，2016（02）：102-105.
[6] 姚志敏.最短路径问题Dijkstra算法的改进[J].数字技术与应用，2016（11）：133.
[7] 任伟建，左方晨，黄丽杰.基于GIS的Dijkstra算法改进研究[J].控制工程，2018，25（02）：188-191.
[8] 韩建昌.我国通用航空文化建设研究[D].西北工业大学，2016.
[9] 张三彬，张永生，近圆.轨逍遥感卫星星下点轨迹的计算[J].测绘学院学报，2001，18（4）：257-259.
[10] 王树西，李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学，2014，41（06）：217-224.
作者简介：
章 胤（1978-），男，硕士，讲师.研究领域：微分方程数值解，数学建模.
李瑞敏（1996-），女，本科生.研究领域：统计学.
郝茂林（1995-），男，本科生.研究领域：信息与计算科学.
王嘉瑜（1996-），女，本科生.研究领域：统计学.
孙鹏越（1998-），男，本科生.研究领域：统计学.
高 琪（1997-），女，本科生.研究领域：会计.
摘 要：由于卫星在军事领域的应用，卫星侦察下的军事运输路线选择得到广泛关注。本文通过分析卫星在其星下点的轨迹，并生成道路缓冲区，借助地理信息系统（GIS）和改进的Dijkstra算法，为卫星侦察下的最优路径选择提供了更优途径。将该方法应用于实际问题中，程序运行所用时间为7.44秒，而经典Dijkstra算法运行时间为16.83秒，改进后的Dijkstra算法相比经典算法节约了近10秒，一定程度上能使相关最优选择问题的效率得到提高。
关键词：卫星运动；公路运输；路线选择；GIS；Dijkstra算法
中图分类号：TP301.6 文獻标识码：A
1 引言（Introduction）
随着空间军事化的高速发展，卫星侦察因其可以获得全天候、大范围、近实时的战场信息，被认为是从外层空间采集地理信息的强有力的手段。为了保护国家机密，在军事运输过程中必须要躲避航天卫星的侦察并要在规定时间内尽快到达目的地。因此，快速生成安全的最短运输路线，躲避卫星侦查，实现安全运输显得尤为重要。
国内外对军事运输路线选择的研讨处于发展完善阶段。Rui Neves-Silva等人提出利用扩展的Dijkstra算法计算灾害中撤离人员的替代路线[1]。Akshay Kumar Guruji等人利用在碰撞阶段之前确定启发式函数的值来代替初始化的一种路径规划算法，以寻找机器人工作时的无碰撞路径，该算法减少了问题处理时间[2]。Xiu Li Gao等人研究改进的Dijkstra算法解决动态路径选择问题[3]。在国内，王辉等人提出利用Dijkstra算法和改进的蚁群算法解决泊车系统的路径规划问题[4]。沈睿等人使用GIS数据模型和改进的Dijkstra算法，缩短了智能交通系统寻求最短路径的搜索时间[5]。姚志敏提出了将Dijkstra算法总计算步数由原来的步减少为不到步的方法[6]。
本文结合卫星的运行轨迹和覆盖范围，以经典Dijkstra算法为基础，对算法进行一定的改进，提高了在卫星影响下躲避卫星侦察的最优公路运输路线选择的效率和准确性，并借助GIS系统进行模拟。
2 基于Dijkstra算法的路径选择模型（The path
selection model based on Dijkstra algorithm）
2.1 地理信息系统
地理信息系统（Geographic Information System，GIS）是用于不同层次的规划、管理与决策所需要的信息粒度与空间信息的图像表达（可视化）。GIS起源于专题地图，但又高于专题制图。在数字环境下，地图信息成为GIS的基础信息与专题信息的载体，一方面是为了通过图形信息压缩来保证地图的可读性，而更重要的是还负担着生成GIS多尺度数据库的新使命。对于以道路网为代表的人工线状物体集合，利用赋权图原理和结点度的信息使其结构化，进而对其进行全局性评价[7]。在地理信息系统中，道路交叉点和道路分别构成道路交通网络中的点集合和边集合。其中，通过收集点矢量要素和边矢量要素的属性字段，来创建边和点之间的权重属性。如道路的长度、道路的类型、道路的宽度等都可以转换为道路权重。该模型以对道路复杂性适应度高的Dijkstra算法为基础。
2.2 卫星轨道和星下点轨迹
卫星轨道是卫星在获得某一初始水平速度后，可以环绕地球飞行的运行轨迹。根据开普勒第一定律，卫星运转轨道的平面，是一个以地心为其中的一个焦点的椭圆。决定卫星运行轨道的参数主要有六种[8]，分别是长轴a、偏心率e、轨道倾角i、升交点赤经、近地点幅角和过近地点时刻t。卫星的星下点是指卫星和地心的连线与地面的交点。星下点轨迹是因卫星运动与地球的自转使得星下点在地球表面进行移动所形成的轨迹。由于地球自转，卫星星下点轨迹的前一圈与后一圈一般不重合。当考虑地球自转时，卫星的星下点轨迹计算公式[9]为：
上述公式中：表示地心纬度、表示地心经度、表示卫星平均角速度、i表示轨道倾角、表示卫星升交点相对经度零点的西退速率、表示卫星经过升交点时的经度、表示卫星经过升交点以后经历的时间。
2.3 卫星覆盖范围
以卫星在当前时刻下，在地面上所有能观察到卫星的点的集合，作为卫星的地面覆盖区域。从理论上来说，如图1所示，卫星到地球表面的两条切线、之间的部分便是卫星的地面覆盖区域。但由于最小观察角的因素，实际的卫星覆盖规模会稍有缩小（即图1中、以内的位置）。同该区域，也就是以卫星 在当前时刻下，所要研究的缓冲区（对应的星下点 为中心，以所对应弧长为半径的地面区域）。在实际地理应用中，将地球视为圆球，单颗卫星的覆盖范围视为是以星下点轨迹为中心，宽度为的条形域。
2.4 影响因素简化
影响运输因素有很多，例如运载工具的种类、道路的交通状况（如红绿灯个数、堵塞程度）、道路上的障碍（如壕沟、涵洞和桥梁）、部队行驶时的指挥人员和驾驶人员的技能，以及当时的气象条件等都是影响军事运输的因素。本文对上述因素不予考虑，仅考虑卫星侦察对道路选择的影响。仅考虑高速公路、县道、省道和国道这四种类型的道路。
2.5 经典Dijkstra算法的主要原理
经典Dijkstra算法是一种通过比较再添加的模型，也称双标记法[10]。并且该算法只适用于边权重均非负的赋权图。对于图，其中V表示顶点集，E表示边集，W表示权集。对图G中的每一点进行标号，其中是从源点s开始到第i个节点的最短路径长度，是第i个节点的直接前趋。其基本思路如下：
（1）对参数进行初始化。令，并标记s点。其他为，均为空。
（2）对于任意未标记的节点j，求。其中表示已标记的节点k到源点s的距离，表示从节点k到节点j的距离。
（3）标记i节点，使得，并取。
（4）重复（2）（3）步，直到所有点的已标记，算法运行完毕。
2.6 Dijkstra算法理解与改进
从2.3中的算法过程中可以看出，每个节点要标记，需要比较其所连接的所有边的最小值，并且最终要标记所有的节点，算法才可以结束。也就是说，对于一张图来说，图中的节点越多，运行算法的时间越长。而对于实际道路中，因地理因素的影响，两地之间的最短距离，往往不包括以两点距离为直径的圆以外的点，并且对于图中边的权值与实际道路长度成正相关，即对于所考虑节点距离较远的节点，显然没必要考虑。所以对于算法遍历的点的数量，可以选择性遍历，在以源点与所求节点欧氏距离为直径的圆内遍历，可进一步减少了循环比较的次数，从而提高算法的运行效率。
在Dijkstra算法运行步骤（2）中，对于遍历所有未标记的节点，传统的Dijkstra算法关于节点的遍历是无序的。我们知道算法要对所有点遍历是不可避免的，但如果图中节点有些权值明显大于其他权值而又要先遍历，到某个节点的最短路径加经过该节点边的直接距离之和中取最小值，在进行最小值判断的时候，权值较大的边会在循环中比较多次，这会制约算法的效率。如果在计算机运行前得到权值的排序，利用这样的排序可以将权值较小的优先比较，那么在与其他边比较的过程中，可以直接舍去一些权值较大的边，从而可以提高算法效率。
引入顺序数组，对节点数据结构加入筛选属性scr，改进的Dijkstra算法的主要思路如下：
（1）初始化源点数据，记scr值为0。对所有边的权重汇总升序编号存入数组中。
（2）在以出发点到汇点为直径的圆，将覆盖到的点。
（3）对圆中未标记的节点j，依数组D的次序，求。其中表示已标记的节点k到源点s的距离，表示从节点k到节点j的距离。
（4）标记i节点，使得，并取。
（5）重复（2）（3）（4）步，直到全部点的已标记，算法运行完毕。
对于增加的卫星过顶因素，以卫星过顶时的缓冲区为参考，一方面减少了所遍历的点的个数，但另一方面会阻碍原始最短路径的选择，并且缓冲区会随着时间规律性移动。
为了解决这些问题，将卫星过顶的缓冲区等效为车辆沿原始最短路行驶下的缓冲区，将经过缓冲区以后的路段进行二次处理。以重新进入缓冲区的节点作为新的源点，重新寻找最短路径，每找到一个中间点，将该点作为新的源点，再次重新寻找最短路径，直到离开卫星缓冲区。
3 应用与实现（Application and implementation）
在Arcgis 10.2，Orbitron 3.71等软件中对算法进行实现。利用Orbitron 3.71获取卫星信息，利用Arcgis 10.2获取地理地图并对其数据库进行处理，利用Arcgis 10.2中自带的Python 2.7脚本实现算法。
3.1 卫星过顶轨迹
选择恰当的卫星，使其星下点轨迹经过所研究的道路。由于卫星不断运动，故设置每1分钟更新一次卫星位置，如图3所示。通过卫星各项参数，计算出卫星扫描范围，生成缓冲区。
3.2 最短路径生成
考虑所选卫星经过的地理区域进行试验，利用Arcgis 10.2绘制河北省秦皇岛市—唐山市地图，地籍数据采集1：10000；经过计算，共得到4597个道路交叉点。假设高速公路行驶时速为匀速100公里/小时，普通公路行驶时速为匀速50公里/小时，不考虑行驶过程中的加、减速时间；假设卫星的覆盖面带是以星下点轨迹为中心，宽度为固定值的条带；假设A地和B地之间有多条路相连，在运输过程中如果按未考虑卫星影响因素生成的最短路径在卫星的覆盖范围内，那么依据卫星所在位置和覆盖范围在卫星覆盖区域外寻找路径或者原地等待。如果经过区域没有被卫星覆盖，那么依照原路行驶；不考虑车队长度对避开卫星的影响。
若采用经典Dijkstra算法脚本运行，因经过缓冲区以后，缓冲区之内的点再次加入，节点最短路径得到更新，所以最终得到的路径并不是在缓冲区影响下的最短路径。采用改进的方法，所生成的道路并不是起点到终点的最短路，而是最短路的近似。其原因在于缓冲区是动态移动的，如按原始选择的道路行驶将会与缓冲区相遇。于是选择更换道路，在卫星无法侦察到的其余道路中选择最短路。
选择以河北省秦皇岛市（119.714°E，39.946°N）为起点，以唐山市（118.172°E，39.615°N）为终点，经过G1高速，杨柏路，再到唐古路，最终到达目的地，途中紅色标线即为躲避卫星侦察的最短路径。通过对比发现，利用改进后的算法，根据卫星进入的时刻，重新记录新起点，程序运行所用时间为7.44秒，而经典算法所运行时间为16.83秒，相比经典算法节约了近10秒，一定程度上缩短了路径选择时间。
4 结论（Conclusion）
本文基于卫星星下点轨迹、卫星覆盖范围和Dijkstra算法的特点，并借助地理信息系统，建立了基于改进的Dijkstra算法躲避卫星侦察的路线选择模型，并通过软件进行了实现，满足了军事运输过程中对隐蔽性和快速性的要求。但本文在对道路进行选择时，仅考虑了常见的道路类型。算法效率虽然得到提高，但也减少了道路选择，使得所求得的距离与实际最短路仍有差距。同时，由于道路限制等其他复杂原因，无法求得真正意义上的最短路径，只能最大程度的接近，也是接下来进一步研究的重点。
参考文献（References）
[1] Rui Neves-Silva，George A.Tshirintzis，Vladimir Uskov，et al.An Extended Dijkstra's Algorithm for Calculating Alternative Routes for Evacuee Agents in Disaster Simulation[J].Frontiers in Artificial Intelligence and Applications，2014：262.
[2] Akshay Kumar Guruji，Himansh Agarwal，D.K.Parsediya.Time-efficient A*Algorithm for Robot Path Planning[J].Procedia Technology，2016：23.
[3] Xiu Li Gao，Tian Jun Hu，Jia Zheng.Research on Dynamic Path Selection Improved Dijkstra Algorithm[J].Advanced Materials Research，2014（1006）：3382.
[4] 王辉，朱龙彪，王景良，等.基于Dijkstra-蚁群算法的泊车系统路径规划研究[J].工程设计学报，2016，23（05）：489-496.
[5] 沈睿，朱学君.基于GIS的最優路径选择的设计与实现[J].工业仪表与自动化装置，2016（02）：102-105.
[6] 姚志敏.最短路径问题Dijkstra算法的改进[J].数字技术与应用，2016（11）：133.
[7] 任伟建，左方晨，黄丽杰.基于GIS的Dijkstra算法改进研究[J].控制工程，2018，25（02）：188-191.
[8] 韩建昌.我国通用航空文化建设研究[D].西北工业大学，2016.
[9] 张三彬，张永生，近圆.轨逍遥感卫星星下点轨迹的计算[J].测绘学院学报，2001，18（4）：257-259.
[10] 王树西，李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学，2014，41（06）：217-224.
作者简介：
章 胤（1978-），男，硕士，讲师.研究领域：微分方程数值解，数学建模.
李瑞敏（1996-），女，本科生.研究领域：统计学.
郝茂林（1995-），男，本科生.研究领域：信息与计算科学.
王嘉瑜（1996-），女，本科生.研究领域：统计学.
孙鹏越（1998-），男，本科生.研究领域：统计学.
高 琪（1997-），女，本科生.研究领域：会计.
