矩阵迭代和Dijkstra两种算法在交通运输路径选择中的对比

本文基于矩阵迭代算法及Dijkstra算法，对两者在最短路径问题中的差异性进行了对比。结果表明：Dijkstra算法可一次求得一点到其他各点的最小阻抗，该算法在进行最短路径的计算时，需要对相邻点进行反复搜寻，计算效率较低，收敛速度较慢。矩阵迭代算法没有严格路径次序限制迭代顺序，可实现算法并行计算，计算速度较高。在阻抗矩阵为对称矩阵时，在经过迭代后，得到的矩阵仍为对称矩阵，这样可使每次迭代的计算量得到减少。通过在重庆市路网上随机选取8个终点及起点，对起始点1点到8点的最短路径及阻抗进行计算表明，Dijkstra算法所用时间为0.673s，迭代矩阵算法所用时间为0.501s，矩阵迭代算法的计算速度更快。在矩阵4×4、6×6、8×8中，矩阵迭代算法的运算时间均比Dijkstra算法的运算时间要小，其迭代次数次数也远远小于Dijkstra算法的迭代次数，这进一步表明，矩阵迭代算法的计算效率要比Dijkstra算法的计算效率高。

【关键词】Dijkstra算法 矩阵迭代算法 交通 阻抗

1 引言

随着我国经济发展越来越快，城市交通运输路径也日趋紧张，在我国大中型城市中，普遍存在公共交通结构的不合理状况[1-4]。城市公共交通网络由众多路径及网络节点构成。由于城市人口和城市规模的不断增长，优化交通运输路径，解决交通出行者出行时间最小、服务最大化、线网效率最大等，方便居民出行[5-7]。在城市交通严重堵塞时，要使交通出行者出行便利，则必须对最短交通路径及交通状态信息进行实时全面了解；在一定程度上，这种信息诱导作用能对重点道路的拥堵起到缓解作用[8]。最短路径的算法有多种，对各种算法进行分析、理解、应用，比较这些算法的在实际应用效率，具有非常重要的实用意义[9-11]。通常情况下，典型最短路径问题算法有两种，分别为矩阵迭代算法、Dijkstra算法。本文基于这两种典型算法，对两者在最短路径问题中的差异性进行了对比，方便交通出行者对交通运输路径的选择。

2 最短路径及路网阻抗

在交通流分配中，最基本的算法就是最短路径算法。最短路径是指在一个网络中，已知相邻节点间的线路长度，要在某一起点到某一终点间找出一条长度最短的路线。在交通领域，最短路径研究较多，在路网中，因受道路条件、道路绕行距离、交通条件影响，使得不同交通路径，所需交通费用有一定的差异。在广义上，交通费用包括道路通行时间、通行距离、燃料的使用等；在狭义上，道路通行时间是阻抗，或将影响出行的其它因素进行折算，转化成通行时间，将其作为道路网交通阻抗，交通阻抗最小的路径就是最短路径。图1为路网的阻抗，表1为道路的可用阻抗矩阵。

3 Dijkstra算法和矩阵迭代算法

3.1 Dijkstra算法

最短路径使用最广泛、最基本的算法就是Dijkstra算法，在求网络中某一节点到其他各节点的最短路径时，网络中的节点被Dijkstra算法分成三部分，分别为最短路径节点、临时标记节点、未标记节点。在算法开始时，源点经初始化，转为最短路径节点，其他节点则为未标记节点。在执行算法时，从最短路径节点扩展到相邻节点，非最短路径节点的相邻节点每次都要修改为临时标记节点，对权值是否更新进行判断，权值最小节点从全部的临时标记节点中提取，在修改为最短路径节点后，将其作为下次扩展源，重复前面步骤，在全部的节点做过扩展源后，结束算法。

Dijkstra算法属于比较经典的最短路径算法，它可对一点到网络内所有节点最小阻抗进行计算，并将相应最短路径推算出。Dijkstra算法计算步骤共5步，第一步是将Dijkstra算法起始点进行标号，记为P，且P（o）=0，其余节点标号为T，且除T（0）外，其余节点的T（i）=∞；第二步是将o点相邻点向量r找出，即dor（i）≠∞，对所有标号为T的值进行比较，找出最小值，即P（k），T最小时所在的点为k点；第三步是按照第二步方法，将k作为起始点，满足T（r（j））=minT（r（j）），P（k）+dkr（i），将最小值所在点k/找出，记P（k/）；第四步是迭代第三步，在全部节点被标志为P后，则求出了o点到其余节点的最小阻抗；第五步是根据所需，对目标点进行查询，以目标点d为起始点，将满足式P（j）=dij+P（i）的i点找出，最短路径中j的前一点就是i点，对i点之前的点进行继续搜索，同样根据P（j）=dij+P（i），直到搜索起点o，图2为Dijkstra算法程序流程图。

3.2 矩阵迭代算法

矩阵迭代算法首先要构造距离矩阵，在矩阵中，给出了节点间经过一步到达某一点的距离，见图3，通过距离矩阵的迭代运算，两步到达某一点的最短距离就得到了。因此，使用矩阵迭代算法研究最短路径问题时，各出行节点间最短路线要知道。

在D（4）=D（3）时，具有最短距离矩阵，通过矩阵，可将最短距离计算出。通过反向追踪，对相应最短路线进行确定。

矩阵迭代法指的是从路径集合中进行挑选，将最短路径分步选出来，完成矩阵迭代，则表明可计算出每一对od点间的最短路径。迭代矩阵算法思想类似于Dijkstra，不同的是其采用矩阵形式对最短路径问题的进行思考，也就是在od两点间，尝试性选择中间路径，计算每个可能的中间路径，并将最小节点选出，并进行迭代计算，得出到达该最短路径是要经过几个中间节点。当所有节点最短路径迭代全部求出后，矩阵迭代结果保持稳定，不再变化，这时表明迭代结束。

矩阵迭代算法的计算步骤共4步，第一步是给定od，其阻抗方阵为D，D1=D，按照公式dij（2）=min（di1（1）+d1j，di2（1）+d2j，…，din（1）+dnj），n表示矩阵阶数n，i=1～n，j=1～n。根据此公式，将两步到达目的地最小阻抗计算出，D2为得到的新矩阵。当dik+dkj达到最小时，将k值记为k（1），也就是最短路径中的一点；第二步是根据公式dij（3）=min（di1（2）+d1j，di2（2）+d2j，…，din（2）+dnj），n表示矩阵阶数n，i=1～n，j=1～n，得到D3。最小值对应点记为k（2）；第三步则依次类推，dij（m）=min（di1（m-1）+d1j，di2（m-1）+d2j，…，din（m-1）+dnj），n表示矩阵阶数n，i=1～n，j=1～n，得到Dm，最小值对应点记为k（m-1），直到Dm=Dm-1；第四步是对目标最小阻抗od即dodm进行搜索，i、j两点间最小阻抗表示为dijm。在标志点o，k（1），k（2），…，k（m-1），d中，x取最短路径，为避免某些点会出现重复，按照didm=dik+dkdm的路径顺序原则进行确定，i起始于o点，根据标志点顺序，依次进行检验，最短路径就是符合要求的点向量。图4为矩阵迭代算法程序流程图。

4 两种算法的比较

通过MatLab平台，进行矩阵迭代算法、Dijkstra算法的编程，MatLab能将计算过程及结果显示出来，通过profiler功能，能将计算时间显示出来。

4.1 最短路径收敛性

矩阵迭代算法、Dijkstra算法的收敛特性由路阻矩阵及计算思路特点决定。因此，使用用计算机计算是可行的。在相邻节点，Dijkstra寻找过程中，向目标节点步步靠近，当最后的终止条件满足后，达到查询终点，起始点到其他点的最小路径能计算出。因路阻矩阵特殊性，在矩阵迭代算法中，矩阵对角线位置元素均为零，目标节点就是最终收敛点，矩阵收敛的充要条件是对角线上的零元素。

4.2 两种方法异同点

相比于矩阵迭代算法而言，使用Dijkstra算法，可将一点到其他各点的最小阻抗一次性求得，根据最短路径，最短路径经过的节点可依次得到，在进行最短路径的计算时，需要反复进行，同时不能颠倒起始点到其他各点最小阻抗的计算顺序，按照步骤严格进行，因而，Dijkstra算法计算效率低，收敛速度较慢。相比于Dijkstra算法而言，矩阵迭代算法则非常简洁，要求不苛刻，矩阵迭代计算效率提高的方法有三个比较可行。第1个是在矩阵迭代算法中，每一步只要遵循dij（m）=min（di1（m-1）+d1j，di2（m-1）+d2j，…，din（m-1）+dnj），n表示矩阵阶数n，i=1～n，j=1～n原则，在i，j间，其迭代顺序限制不严格，可并行进行计算，这样就可使计算速度大大提高；第2个是可以同时设计程序，使计算值避免出现∞数据，只对非∞数据与其下标策略进行存取，这样内存空间就得到节约，从而使计算效率得到提高；第3个由于阻抗矩阵属于对称矩阵，在不断进行迭代后，阻抗矩阵仍属于对称矩阵，根据这一特征，每次迭代的计算量可减少。若道路阻抗是负数，则可能Dijkstra算法会出现无效，在矩阵迭代算法中，道路阻抗可为负数，图5为矩阵迭代算法中的道路阻抗。

4.3 计算效率比较

在计算程序中，MatLab内含的程序测试器profiler，具有一定的优越性，因此本研究采用MatLab平台进行Dijkstra算法、矩阵迭代算法的编程，并计算同一路网，在得到相同结果时，对各个计算效率指标进行比较，在计算效率方面，显示Dijkstra算法、矩阵迭代算法的不同。在重庆市路网上随机选取8个终点及起点，对起始点1点到8点的最短路径及阻抗进行计算。在程序算法分析里，时间复杂度是非常重要的内容，时间复杂度通常是指算法中执行基本运算的次数，影响时间复杂度的因素较多，本研究主要对影响时间复杂度的重要因素进行分析，比较Dijkstra算法、矩阵迭代算法的时间复杂度，表2为两种方法计算时间，表3为Dijkstra算法的计算结果，表 4为矩阵迭代算法计算结果。

对起始1点到8点的最小路阻采用Dijkstra算法进行计算，结果为P（8）=5，其相应的最短路径为14568。对起始1点到8点的最小路阻采用迭代矩阵算法进行计算，结果为D1（1，8）=5，其相应的最短路径为14568，结果相同。但Dijkstra算法和迭代矩阵算法的计算效率有一定的差距，从表2可以看出，Dijkstra算法所用时间为0.673s，迭代矩阵算法所用时间为0.501s，矩阵迭代算法的计算速度更快。矩阵迭代法可全部算出路网中两点间的最小阻抗，Dijkstra算法仅能算出起始点到其他各点间的最小路阻；路网中的节点远比8多很多，采用Dijkstra算法要进行上万次的循环，使计算速度大幅降低，使用迭代矩阵算法，则迭代次数远比节点数小，因此，迭代矩阵算法优势更大，同时对于路阻为负的路网，可通过矩阵迭代进行计算，即对于更广泛的最短路径，迭代矩阵算法能适合其计算要求。

基本运算次数与运算所需时间的乘积即就是算法执行时间，为进一步比较Dijkstra算法和迭代矩阵算法的计算效率，本研究将两程序对中取出4×4、6×6、8×8共3个矩阵进行计算，对运算时间进行比较，分别对交通运输路网中任意2点间的最小阻抗进行计算，表5为计算时间参数数据。

从表5可以看出，在矩阵4×4、6×6、8×8中，矩阵迭代算法的运算时间均比Dijkstra算法的运算时间要小，其迭代次数次数也远远小于Dijkstra算法的迭代次数，这进一步表明，矩阵迭代算法的计算效率要比Dijkstra算法的计算效率高。

5 结论

本文基于矩阵迭代算法及Dijkstra算法，对两者在最短路径问题中的差异性进行了对比，得出以下结论：

（1）通过Dijkstra算法，对于一点到其他各点的最小阻抗可一次求得，最短路径经过的节点可依次得到，该算法在进行最短路径的计算时，需要对相点进行反复搜寻，计算效率较低，收敛速度较慢。

（2）矩阵迭代算法是元素间比较、数列间相加的过程，特点是简单快捷。矩阵迭代算法没有严格路径次序限制迭代顺序，可实现算法并行计算，计算速度较高。在阻抗矩阵为对称矩阵时，在经过迭代后，得到的矩阵仍为对称矩阵，这样可使每次迭代的计算量得到减少。

（3）通过在重庆市路网上随机选取8个终点及起点，对起始点1点到8点的最短路径及阻抗进行计算表明，Dijkstra算法所用时间为0.673s，迭代矩阵算法所用时间为0.501s，矩阵迭代算法的计算速度更快。在矩阵4×4、6×6、8×8中，矩阵迭代算法的运算时间均比Dijkstra算法的运算时间要小，其迭代次数次数也远远小于Dijkstra算法的迭代次数，这进一步表明，矩阵迭代算法的计算效率要比Dijkstra算法的计算效率高。

参考文献

[1]张美玉，简b峰，侯向辉，等.Dikstra算法在多约束农产品配送最优路径中的研究应用[J]，浙江工业大学学报，2012，40（03）：321-326.

[2]Niehols，Jolin M.A major urban earthquake： planning for arma-geddon[J]，Landscape and Urban， 2005，73，2：136-154.

[3]刘洪丽，顾铭.矩阵迭代法在物流中心选址中的应用分析[J]，现代商贸工业，2013（20）：64-67.

[4]丁浩，苌道方.基于Dijkstra算法的快递车辆配送路径优化[J]，价值工程，2014（03）：15-18.

[5]郭瑞军，王晚香.基于矩阵迭代法的出租车合乘最短路径选择[J]，大连交通大学学报，2011，32（04）：28-32.

[6]任鹏飞，秦贵和，董劲男，等.具有交通规则约束的改进Dijkstra算法[J]，计算机应用，2015，35（09）：2503-2507.

[7]王树西.改进的Dijkstra最短路径算法及其应用研究[J]，计算机科学，2012，39（05）：223-228.

[8]刘春年，邓青菁.应急决策信息系统最优路径研究-基于路阻函数理论及Dijkstra算法[J]，灾害学，2014（03）：7.

[9]潘若愚，褚伟，杨善林.基于Dijkstra-PD-ACO算法的大城市公交线路优化与评价方法研究[J]，中国管理科学，2015，23（09）：106-116.

[10]王佳，符卓.综合客运枢纽接运公交线路优化设计[J]，系统工程，2012，30（05）：101-106.

[11]高明霞.基于双层规划的交通疏散中车辆出发与交通控制综合优化[J]，中国管理科学，2014，22（12）：65-71.

作者简介

肖鹏（1980-），男，江苏省镇江市人。硕士学位。现为江苏城乡建设职业学院基础部讲师。研究方向为应用数学。

作者单位

江苏城乡建设职业学院 江苏省常州市 213147