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

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

2、算表明， Dijkstra 算 法所用时间为 0.673s ，迭代矩阵算法所用时间为 0.501s ，矩阵 迭代算法的计算速度更快。在矩阵4X4、6X 6、8X8中，矩阵迭代算法的运算时间均比 Dijkstra 算法的运算时间要小，其迭 代次数次数也远远小于 Dijkstra 算法的迭代次数，这进一步表 明，矩阵迭代算法的计算效率要比 Dijkstra 算法的计算效率高。1 引言 随着我国经济发展越来越快，城市交通运输路径也日趋紧 张，在我国大中型城市中， 普遍存在公共交通结构的不合理状况 1-4 。城市公共交通网络由众多路径及网络节点构成。由于城 市人口和城市规模的不断增长， 优化交通运输路

3、径， 解决交通出 行者出行时间最小、服务最大化、线网效率最大等，方便居民出 行5-7 。在城市交通严重堵塞时，要使交通出行者出行便利， 则必须对最短交通路径及交通状态信息进行实时全面了解； 在一 定程度上，这种信息诱导作用能对重点道路的拥堵起到缓解作用 8 。最短路径的算法有多种，对各种算法进行分析、理解、应 用，比较这些算法的在实际应用效率， 具有非常重要的实用意义 9-11 。通常情况下，典型最短路径问题算法有两种，分别为矩 阵迭代算法、 Dijkstra 算法。本文基于这两种典型算法，对两 者在最短路径问题中的差异性进行了对比， 方便交通出行者对交 通运输路径的选择。2 最短路径及路网阻

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

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

6、法属于比较经典的最短路径算法，它可对一点 到网络内所有节点最小阻抗进行计算，并将相应最短路径推算 出。 Dijkstra 算法计算步骤共 5 步，第一步是将 Dijkstra 算法 起始点进行标号，记为 P,且P (o) =0,其余节点标号为T,且 除T (0)外，其余节点的T (i ) =s；第二步是将o点相邻点向 量r找出，即dor ( i )工鸡，对所有标号为 T的值进行比较， 找出最小值，即 P(k)， T 最小时所在的点为 k 点；第三步是按 照第二步方法， 将 k 作为起始点， 满足 T( r( j )=minT( r( j )， P(k)+dkr( i )，将最小值所在点 k/

7、找出，记 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，通过距离矩阵的迭代运 算，两步到达某一点的最短距离就得到了。因此，使用矩阵迭代

8、 算法研究最短路径问题时，各出行节点间最短路线要知道。在 D( 4)=D( 3)时，具有最短距离矩阵，通过矩阵，可将 最短距离计算出。通过反向追踪，对相应最短路线进行确定。矩阵迭代法指的是从路径集合中进行挑选， 将最短路径分步 选出来，完成矩阵迭代，则表明可计算出每一对 od 点间的最短 路径。迭代矩阵算法思想类似于 Dijkstra ，不同的是其采用矩 阵形式对最短路径问题的进行思考，也就是在 od 两点间，尝试 性选择中间路径， 计算每个可能的中间路径， 并将最小节点选出， 并进行迭代计算，得出到达该最短路径是要经过几个中间节点。 当所有节点最短路径迭代全部求出后，矩阵迭代结果保持稳定，

9、不再变化，这时表明迭代结束。矩阵迭代算法的计算步骤共 4步，第一步是给定od，其阻抗方阵为 D, D仁D 按照公式 dij ( 2)=min (di1 ( 1)+d1j，di2(1) +d2j，din (1) +dnj ), n 表示矩阵阶数 n, i=1 n,j=1n。根据此公式，将两步到达目的地最小阻抗计算出，D2为得到的新矩阵。当 dik+dkj 达到最小时，将 k 值记为 k(1)， 也就是最短路径中的一点； 第二步是根据公式 dij ( 3)=min(di 1(2) +d1j , di2 (2) +d2j，din (2) +dnj), n 表示矩阵 阶数n, i=1n, j=1n,得

10、到D3o最小值对应点记为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点，根据 标志点顺序,依次进行检验,最

11、短路径就是符合要求的点向量。图 4 为矩阵迭代算法程序流程图。4 两种算法的比较通过 MatLab 平台,进行矩阵迭代算法、 Dijkstra 算法的编 程, MatLab 能将计算过程及结果显示出来, 通过 profiler 功能, 能将计算时间显示出来。4.1 最短路径收敛性矩阵迭代算法、 Dijkstra 算法的收敛特性由路阻矩阵及计 算思路特点决定。因此,使用用计算机计算是可行的。在相邻节 点, Dijkstra 寻找过程中,向目标节点步步靠近,当最后的终 止条件满足后, 达到查询终点, 起始点到其他点的最小路径能计 算出。因路阻矩阵特殊性，在矩阵迭代算法中，矩阵对角线位置 元素均为零

12、， 目标节点就是最终收敛点， 矩阵收敛的充要条件是 对角线上的零元素。4.2 两种方法异同点相比于矩阵迭代算法而言，使用 Dijkstra 算法，可将一点 到其他各点的最小阻抗一次性求得， 根据最短路径， 最短路径经 过的节点可依次得到， 在进行最短路径的计算时， 需要反复进行， 同时不能颠倒起始点到其他各点最小阻抗的计算顺序， 按照步骤 严格进行，因而， Dijkstra 算法计算效率低，收敛速度较慢。 相比于 Dijkstra 算法而言，矩阵迭代算法则非常简洁，要求不 苛刻，矩阵迭代计算效率提高的方法有三个比较可行。 第 1 个是 在矩阵迭代算法中，每一步只要遵循 dij ( m)=min

13、(di1 (m-1) +d1j , di2 (m-1) +d2j，din (m-1) +dnj), n 表示矩阵阶 数n, i=1n, j=1n原则，在i , j间，其迭代顺序限制不严 格，可并行进行计算，这样就可使计算速度大大提高；第 2 个是 可以同时设计程序，使计算值避免出现数据， 只对非数据与 其下标策略进行存取, 这样内存空间就得到节约,从而使计算效率得到提高； 第 3 个由于阻抗矩阵属于对称矩阵,在不断进行迭代后,阻抗矩阵仍属于对称矩阵,根据这一特征,每次迭代的计 算量可减少。若道路阻抗是负数,则可能 Dijkstra 算法会出现 无效,在矩阵迭代算法中,道路阻抗可为负数,图5 为

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

15、的重要因素进行分析，比较 Dijkstra 算法、矩阵迭代算法的时间复杂度，表 2 为两种方法 计算时间，表 3 为 Dijkstra 算法的计算结果，表 4 为矩阵迭代 算法计算结果。对起始 1点到 8 点的最小路阻采用 Dijkstra 算法进行计算， 结果为P( 8) =5,其相应的最短路径为1-4-5-6-&对起始 1 点到 8 点的最小路阻采用迭代矩阵算法进行计算，结果为 D1 (1， 8) =5，其相应的最短路径为 1-4-5-6-8，结果相同。 但 Dijkstra 算法和迭代矩阵算法的计算效率有一定的差距，从 表 2 可以看出， Dijkstra 算法所用时间为 0.673s

16、，迭代矩阵算 法所用时间为0.501s，矩阵迭代算法的计算速度更快。矩阵迭 代法可全部算出路网中两点间的最小阻抗， Dijkstra 算法仅能 算出起始点到其他各点间的最小路阻； 路网中的节点远比 8 多很 多，采用 Dijkstra 算法要进行上万次的循环，使计算速度大幅 降低，使用迭代矩阵算法，则迭代次数远比节点数小，因此，迭 代矩阵算法优势更大， 同时对于路阻为负的路网， 可通过矩阵迭 代进行计算， 即对于更广泛的最短路径， 迭代矩阵算法能适合其 计算要求。基本运算次数与运算所需时间的乘积即就是算法执行时间， 为进一步比较 Dijkstra 算法和迭代矩阵算法的计算效率，本研 究将两程序

17、对中取出4X4、6X6、8X8共3个矩阵进行计算， 对运算时间进行比较， 分别对交通运输路网中任意 2 点间的最小 阻抗进行计算，表 5 为计算时间参数数据。从表 5 可以看出，在矩阵 4X 4、 6X 6、 8X8 中，矩阵迭代 算法的运算时间均比 Dijkstra 算法的运算时间要小，其迭代次 数次数也远远小于 Dijkstra 算法的迭代次数，这进一步表明， 矩阵迭代算法的计算效率要比 Dijkstra 算法的计算效率高。5 结论本文基于矩阵迭代算法及 Dijkstra 算法，对两者在最短路 径问题中的差异性进行了对比，得出以下结论：（ 1）通过 Dijkstra 算法，对于一点到其他各点的最小阻抗 可一次求得， 最短路径经过的节点可依次得到， 该算法在进行最 短路径的计算时，需要对相 ?点进行反复搜寻，计算效率较低， 收敛速度较慢。2）矩阵迭代算法是元素间比较、数列间相加的过程，特 点是简单快捷。矩阵迭代算法没有严格路径次序限制迭代顺序， 可实现算法并行计算， 计算速度较高。 在阻抗矩阵为对称矩阵时，