精品论文基于 Dijkstra 算法的铁路客运中转径路优化余震江，王成良 重庆大学软件学院，重庆（400044） E-mail: ponyzj@, wcl@摘 要：铁路客运中转径路优化，是基于铁路运输网拓扑结构的最优路径算法问题因为具有实际的应用背景，最优路径算法考虑的因素和限制条件比经典最短路径算法复杂得多，其 核心思想还是源于经典最短路径算法本文在经典 Dijkstra 算法的基础上, 对算法和数据结 构进行了改进,并结合应用领域采取了对路网按节点层次编码、将业务逻辑融入搜索过程中 等优化方法，实现了算法的高效性和搜索路径的有效性关键词：最短路径；Dijkstra 算法；铁路网；径路计算0. 引言随着经济社会不断发展和铁路运输能力的提高，铁路成为旅客出行特别是中长途旅客出 行的重要交通方式选择铁路出行的旅客不断增加，由于不可能在任意城市的车站间都开行 直达列车，因此针对旅客出行要求提供合理的乘车方案（路径、车次、中转车站、中转次数 等）成为旅客十分关心的问题最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的研究热点国内外大 量专家学者对此问题进行了深入研究经典的图论与不断发展完善的计算机数据结构及算法 的有效结合使得新的最短路径算法不断涌现[1]。
最短路径问题是资源分配、路线设计及分析 等优化问题的基础,其算法是交通网络分析的核心算法之一在经典Dijkstra 算法中，节点无序地存储在无序表中，每次搜索与当前检查点相邻的节点时，需要遍历所有的节点，成为算法的瓶颈本文结合路网结构、列车等级、经由、停靠 站等业务信息，从算法运行结构和数据存储结构两方面对Dijkstra算法进行优化：一是针对 实际网络特征优化运行结构, 采用堆排序数据结构设计算法，在统一时间复杂度的基础上尽 可能地提高算法的运行效率；二是采用拓扑层次编码路径视图，减少最优路线分析过程中搜 索节点的数量，从而尽快到达目标点；三是采取节点—车次邻接表结构来描述存储铁路网和 车次信息，使搜索的结果是基于车次的而不仅是基于线路的，具有适用性1. 最短路算法思想和优化途径分析1.1 最短路算法简述最短路径算法按照路径搜索实现技术可分为组合技术和代数方法两种组合技术主要 是指标号算法（Labeling Algorithms）,也是大多数最短路算法的核心部分标号算法又分为 标号设定法（Labeling Setting Algorithms,简称LS算法）和标号改正法（Labeling Correcting Algorithms，简称LC算法）。
LS算法又称最短优先算法，最早由荷兰数学家Dijkstra于1959 年提出Dijkstra算法的广泛应用，使其成为标号设定法的代名词[1]LC算法又称列表优先 算法LS 算法在优先级队列处理的每一步, 都能得到一条由源点到其余节点的最短路径,由 此当仅需1:1 最短路径时, 当终点跳出优先级队列时即可结束但LS算法不能处理含负权边 的网络而LC算法处理节点时,可能需要多次进出优先级队列, 因此源点到终点的1:1最短路 径需到算法结束时才能得到LC算法可处理含负权边的网络基于各种运行结构的Dijkstra 算法仍是交通网络最短路径算法的首选 2 -1.2 经典 Dijkstra 算法的主要思想对图G(V,E),设置两个顶点的集合S和T=V-S ,集合S中存放已找到最短路径的结点,集合 T存放当前还未找到的最短路径的长度最短的结点Dijkstra算法的输出结果是以源点V 0为 根的生成树生成树迭代构建，当迭代过程结束，就形成最短路径树对每个结点V i的标 号有三种：距离标号d (i)；父节点标号p(i);结点状态标号s(i)d (i)表示从V 0到其他结点V i 的路径长度初值，w(i,j)表示弧（V i, V j）的权值。
Dijkstra 算法将网络结点分为未标号结 点（Unreached）、临时标号结点(Temporarily Labeled)和永久标号结点(Permanently Labeled) 三种类型求解源点s到其他所有结点的最短路径的基本过程如下：1）初始化对所有结点V i，如果V i不等于V 0，则d (i )=∞, s (i)= Unreached；否则，d(i)=0, s(i)= Temporarily LabeledT←N，如果T为空，则算法结束2）从T标号点中选出加权距离最小的点V jd (j)=min{d (i), V i∈V-S}；s(j)= Permanently Labeled.V j就是当前求得的一条从v0出发的最短路径的终点令 S=S∪Vj.3）对与V j相连的每个结点V k, V k∈V-S如果d(j)+w(j,k)< d(k)，则修改d(k)为d(k)=d(j)+w(j,k)s(k)= Temporarily Labeled4）重复操作2),3）共n -1 次由此求得从V0 出发到图上各个结点的最短路径是依路径 权值递增的序列[6]1.3 优化途径分析从上述算法描述过程可知，第2)、3)步是影响该算法效率的关键。
由于每次搜索最小权 值的结点V j，都需要对V−S集合上的所有结点进行扫描，而这些结点是无序存放在一个链表 或数组中，会花费大量的时间；另外，搜索最小权值的过程中，还会出现某些结点被多次访 问的情况，增加了额外的运算量要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排 列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率这也是目前各种 基于传统的Dijkstra算法的各种优化算法的重要出发点之一另外一个优化途径就是减少路 线分析过程中搜索结点的数量，从而尽快到达目标点另外，针对铁路网进行中转径路计算，就必须首先将铁路网按结点和边的关系抽象为图 的结构，即构建网络的拓扑关系如果用矩阵来表示这个网络，不但所需空间巨大，而且效 率会很低下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及算法运行结构的实 现进行讨论2. 铁路客运网络拓扑结构描述2.1 铁路客运网络的存储结构网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示一般而言，无向 图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和十字链表表示，其优缺 点的比较见表 1[3]最短路径搜索问题一般都采用结点-弧结构的存储结构表示。
这一方面清晰地表达了网络的拓扑结构, 另一方面更加便于Dijkstra 算法的实现采用邻接表类型存储交通网络拓扑 数据结构, 在业界早已达成共识表1 几种图的存储结构的比较名 称 实现方法 优点 缺点 时间复杂度邻接矩阵 二维数组 易判断两点间关系；易求顶点 的度占用空间大 O(n2+m*n)邻接表 链表 节省空间；易求顶点出度 不易判断两点间关系；不易求顶O(n+m)或 O(n*m)点入度十字链表 链表 空间要求较小；易求得顶点的 度邻接多重表 链表 节省空间；易判断两点间的关系结构较复杂 同邻接表结构较复杂 同邻接表铁路客运中转问题，既与线路、车站、站间距离的铁路网信息相关，同时又与车次始发车站、终到车站、中途停靠车站及到开时刻等车次信息相关所需构建的铁路客运网络存储 结构要同时包含路网和开行车次本文采用车次-到站邻接表作为铁路客运网络的存储数据结构表头结点存储指定指定 日期内有效的经过本站停靠的所有列车车次信息；头结点存储到站为某一指定站的信息； 表内结点某车次某停靠站的信息表结点列出所有本站可达的换乘中转站，根据不同的表头 结点可以得到同站的车次序列这样，车次-到站邻接表就表达了包含车站和车次信息的可 达铁路客运网络图,如图1所示[5]。
图1 车次-到站邻接表2.2 铁路客运网络的层次编码当一个人站在全国铁路客运运营示意图前，可以很快地找到其中两个车站间的一条径 路这条径路即使不是最短或最优的，也是比较合理的一条径路这时，人类的思维方法中 的层次策略、方向策略、贪心策略帮助我们快速找到一条径路层次策略会使他优先选择经 过较大且可供选择的中转车次较多的车站；方向策略会使他选择趋向于终点站的径路；贪心 策略会使他选择趋于直线的线路层次策略是人类思维活动的一种重要方式，在解决具有空间特征的问题中常常被采用 层次空间推理是根据一定规则将问题按空间或任务划分来进行推理的空间分析方法划分具 有层次结构的空间对象是分层或分区进行的，每个层次或子区的对象具有相同结构、类型或 操作层次 i+1 是层次 i 的空间子集层次空间中的对象、对象间关系及其操作仅与被划分 成不同层次的同一任务有关[2]例如，在铁路客运中转问题中对客运网络划分的层次的依据 就是中转的便捷程度，具体的就是车站始发、通过的车次的数量在铁路客运网络中提取以下车站：1） 所有车次的始发车站、终到车站，记为 S1；2） 所有省会（直辖市、自治区首府）所在地车站,记为 S2；3） 所有铁路局所在地、分界口车站, 记为 S3；4） 所有客运线路中 3 条及以上线路相交的车站, 记为 S4；5） 所有铁路客运结算站, 记为 S5。
分层表示的铁路客运网络层次图为：1） 高层图：结点由 S1∪S2∪S3∪S4∪S5 组成，边由所有车次被 S1∪S2∪S3∪S4∪S5分割成的区间组成；2） 子图：按照各铁路局管辖范围划分，包括辖区内的车站、线路、车次； 根据起点站 Vs、终点站 Vt 所位于的层次，通过层次图进行径路查询有 4 种情况：1）起点站、终点站都位于高层图，仅需在高程图查询径路，遍历的结点数仅为近 300个；2) 起点站位于高程图，终点站不在高程图首先需要遍历终点站所在子图，得到与终 点站相邻的高程图结点集{Vk}；然后在高层图中查询起点站 Vs 到{Vk}中各点的最短路，取 最小值；3）起点站不在高程图，终点站位于高程图方法同 2）；4）起点站、终点站都不在高程图分别求得与起点站、终点站相邻的高程图结点集， 再进行 1）通过层次图进行最短路查询，有效地减少了需要遍历的结点数量，可以提高算法的运行 效率3. 对 Dijkstra 算法运行结构的优化3.1 当前流行的最短路算法运行结构分析比较最短路算法运行数据结构纷繁多样，各有特色，主要有桶结构法、队列法以及堆栈实现 法DIKBA 、DIKBD 以及 2que 在这方面是比较典型的代表。
2que 虽然是基于图增长理论 的，但是快速搜索技术同样是其算法实现的关键，它用两个 FIFO 的队列实现了一个双端队 列结构来支持搜索过程DIKBA 和 DIKBD 是采用如图 2 所示的桶结构来支持这个运算，其算法的命名也来源 于此在 DIKBA 算法中，第 i 个桶内装有权值落在［b*i, b * (i+1)］范围内的可供扫描的点， 其中 b 是视网络中边的权值分布情况而定的一个常数每一个桶用队列来维护，这样每个点 有可能被多次扫描，但最多次数不会超 b 次最坏情况下，DIKBA 的时间复杂度将会是 O(m*b+n(b+C/b))，其中，C 为图中边的最大权值DIKBD 将点按权值的范围大小分装在两个级别的桶内，高级别的桶保存权值较大的点， 相应的权值较小的点都放在低级别的桶内，每次扫描都只针对低级别桶中的点当然随着点 的插入和删除，两个桶内的点是需要动态调整的。