杨磊 王润杰 张言舟
国防大学联合勤务学院,北京100000
摘要：本文研究目的在于寻找最优的抗疫物资运输路径。Dijkstra算法是计算最优路径的的代表算法，针对其存储效率和计算效率过低问题，提出用邻接表代替权重邻接矩阵、采用双向循环链表进行快速增删、同时利用快速排序对权重距离进行排序的改进方法，最后综合考虑实际道路的综合通行能力对改进的Dijkstra算法进行实例验证。
关键词：Dijkstra算法；路径规划；抗疫物资运输
一、引言
回首过往，人类的历史既是一部发展史、也是一部危机史，危机往往与发展并存。恰如恩格斯所言，“没有哪一次巨大的灾难不是以历史的进步作为补偿的。”[1]纵观古今、横观中外应对疫情迅速爆发的大量实践证明，战胜疫情必须有强有力的物质基础作为坚强支撑。疫情爆发具有很强的隐蔽性和突发性，也会面临口罩、防护服、医疗设备等抗疫物资缺乏的困境。抗疫物资运输供应是在疫情爆发时紧急为疫情爆发地区提供医疗物资保障的特殊物流活动，能够有效提升医疗救援的效率，有效挽回人民的生命财产损失，有效维护社会稳定。因此，在具体的抗疫物资运输路径规划时，如何选择合适恰当的车辆运输路线，以最短时间、最高效率把抗疫物资供应到疫情爆发地区，最大限度挽回人民群众的生命财产，具有一定的现实意义。
二、算法的简介及基本原理
Dijsktra算法用于计算从源节点到所有其他节点的最短代价路径，它是按路径长度递增的次序来产生最短路径的算法[2]。该算法主要特点以起始点为中心向外层层扩展，直至扩展到终点为止[3]，因此可以计算出起点到任意点的计算路径。
根据图论的基本原理，在用Dijkstra算法具体分析的抗疫物资运输路径时，将抗疫物资运输路径转化为图G=（V，E）来表示，V（vertex）表示的是抗疫物资运输路径中的关键节点，E（edge）表示的是抗疫物资运输路径节点与节点之间的距离。根据相关文献[4]，Dijkstra的算法简要步骤如下：
分别定义集合S、集合U和数组distance,集合S为已访问的最短路径的节点信息集合，集合U为未访问的节点信息集合，distance[]数组存放的数值依次为从起点到对应节点的最短距离值。
数据初始化：将起点o加入到集合S中，同时集合U中包含除了起点o之外的其他所有节点。distance[]数组初始化为无穷大∞。
检索：遍历查询集合U中其他所有节点与o的距离值，以便筛选出离当前节点距离长度最短的节点m，将m加入到集合S的同时，将节点m从集合U中移除。
更新：每当集合S加入一个新节点m，都需更新起点o到未访问节点集合U中的所有节点距离。在步骤的情况下，需要对集合U中经过节点m和不经过节点m到达该节点的最短路径做判断选择，如果经过节点m的路径距离要比不经过节点m的路径距离要短，那么distance[]数值更改当前节点的最短路径值。
不断循环遍历步骤和步骤，直到所有节点遍历完成，集合S包含全部节点，集合U为空集，distance[]记录的是起点到任意对应节点的最短路径长度。
三、算法的改进
传统Dijkstra算法虽然是求解最短路径的经典算法，但其在实际运用时由于自身的缺陷，导致算法的时间效率和存储效率偏低。一是存储空间开辟过多。对于一个大型稀疏图而言，用权重邻接矩阵存储需要开辟n*n（n为节点数量）的矩阵的存储空间，此外矩阵中包含了大量的0和∞，也是对计算机存储空间的浪费。二是循环遍历速度有待提高。在步骤更新过程中，需要循环遍历所有与m不直接相连的节点，这无疑限制了计算速度。三是未对集合U中的节点按照距离长短进行排序。如果要找出离中间节点m距离最短的节点，需要做一次循环将所有的节点遍历一遍，进行比较。如果数据量比较大，也会制约计算速度。
针对传统Dijkstra算法的不足，本文将从存储方式和快速排序两个方面，对其进行改进优化。一是对于稀疏矩阵而言，用邻接表代替权重邻接矩阵。同时建立一个双向循环链表存储集合U中的邻接节点，方便删除、修改、查询。二是对于提高循环遍历速度和未排序问题，针对某未访问节点选出相关邻接节点，并对其边的权重进行快速算法排序，实现算法的优化。对改进的Dijkstra算法简明步骤如下：
假设S集合为已访问节点的集合，T集合为已访问节点的邻接点集合，sort[]为待排序节点，distance[]功能不变、定义parent[]用于存放上一节点。
初始化操作。S集合放入起点o，T集合存放起点o的邻接点，sort数组读取T集合数据，distance[]初始化为∞，对加入T集合的节点修改其对应的distance数值。
对已经读取T集合信息的sort[]进行快速排序，找到邻接节点m，如果m是上一节点的所有邻接节点里距离最短的节点的话，将m加入S集合。
利用双向循环链表更新m的所有邻接节点集合，T集合里存放m的未加入S集合的所有邻接节点，并对T集合的所有节点进行一次循环判断，经过节点m和不经过节点m的路径哪个更短，如果经过节点m的路径更短，则修改其parent数组值为节点m。
查找S集合中所有未放入集合S中的相关邻接节点，并存储到sort数组中，找出这些节点距离起点o的路径距离最小值的节点，将数据保存到distance[]和parent[]，并将该节点放入S集合。
重复步骤、、，直至所有节点全部被放入S集合，算法完成，distance数组存放的是从起点o到节点对应的最短距离值，parent数组存放的是从起点到终点的最短路径经过的所有节点。
四、案例验证
现假设某国N市突然发生新冠肺炎疫情。鉴于S市相对发达，医疗物资充足，其接到政府要求对N市疫情爆发紧急提供相关医疗物资，派遣车辆紧急驰援前往N市。下图为从S市出发到N市的交通路线示意图，其中v1代表S市，v9代表N市，v2至v8分别为运输途径中的主要城市，两点之间的数值表示两城市之间的距离，也即边的权重值。
.png)
在实际运输时，不仅仅需要考虑两城市之间的距离，还必须将路面质量、道路性质、行车流量、实时路况、能见度等限制路面通行条件统筹考虑，为简化模型，这里用道路通行的综合能力综合考虑上述条件。经查阅相关文献[5]，可获得道路快速通过能力等级表如表1所示。
.png)
根据本文改进算法，通过MATLAB进行仿真分析。其中节点1代表S市，节点9代表N市，未考虑道路综合通行能力和考虑道路综合通行能力两种情况下分别利用MATLAB进行编程计算，其从S市到N市的抗疫物资运输最优路径示意图如图3和图4所示。
.png)
总结
经过MATLAB仿真可以得出，路径距离上的最短不一定是最优路径。在真实情况下，道路的路面质量、道路性质、行车流量、实时路况、气象能见度等条件都制约着抗疫物资的运输效率，不同的限制条件可能会导致不同的最优路径选择，因此在真实的抗疫物资运输过程中，必须综合考虑各方面的因素，而不能仅仅追求路径的最短。同时现实世界中不仅仅是点与点之间的救援，更有可能的是多个地区向同一个目标地进行抗疫物资运输供应。该情况下模型更为复杂，例如可能存在最优路径重叠问题，从而影响该道路的行车流量。因此应当根据路面质量、道路性质、行车流量、实时路况、气象能见度等情况设计相适应的动态算法。
参考文献
[1]马克思，恩格斯.马克思恩格斯全集：第39卷[M].北京人民出版社，1976:149.
[2]张林广.基于配对堆改进的Dijkstra算法[J].中国图像图形学报，2007,5(12):922-924.
[3]吴必军，李利新，雷小平.基于城市道路数据库的最短路径搜索[J].西南交通大学学报，2003,38(01):80-83.
[4]石晓达，孙连英，葛娜，赵平，李子元.应急资源配送中Dijkstra改进算法的研究[J].北京联合大学学报，2018,32(2):66-69.
[5]曹舒淮，王潇，姜浩然，梁宵，曲芳.改进的Dijkstra算法在应急救援最优路径问题中的应用[J].山东工业技术，2017，(01):144.