改进Dijkstra算法在公共交通出行的研究

2018-11-21张本俊周海娇刘淑琴

物联网技术 2018年11期

张本俊，周海娇，刘淑琴

（江西师范大学物理与通信电子学院，江西南昌 330022）

0 引言

错综复杂的公交路网让人心慌意乱，特别是来到人生地不熟的地方，一条最优交通路线的重要性不言而喻。多种交通方式并存的模式将更符合现代化社会的需求。随着公共交通的多元化和共享单车的盛行，人们出行考虑的不再仅仅是路程问题，而是由时间、换乘和票价等因素决定的综合问题。通常同一路线的公交行程中，最大金额与最小金额差异不大，因此重点考虑少换乘。

Dijkstra算法是求解单源最短路径问题的典型算法。本文考虑到站点间换乘的距离和换乘票价问题，根据用户需求智能分析线路，实现人性化公交线路查询，提供换乘方案的三种可选方向，分别是时间最优、最少换乘和少步行。

1 国内外研究现状

Dijkstra算法通常用来计算加权图中指定节点到其他顶点间的最短距离，算法需遍历所有节点集合，且实现一次后没有为以后的选择留下任何信息，效率较低，尤其在节点数目大时耗时较长，其时间复杂度为O（N2）。

近年来，国内外对此算法的研究已经相对完善，主要针对Dijkstra算法本身和应用进行改进。例如，李健研究的基于Dijkstra最短路径算法的优化研究[1]；韩慧玲、胡红萍研究的Dijkstra算法在公交换乘最短路径中的应用[2]；余震江研究的基于最短路径Dijkstra算法的铁路客运中转路径优化研究[3]；Joseph Kirk使用Dijkstra算法计算沿着图的边的最短（最少成本）路径[4]等。

在换乘方面，目前仍存在下列问题：

（1）只考虑了公交站点，即如何到达，忽略了站点间换乘的距离，而这段距离也应计算在时间损耗中；

（2）一般提供的查询方案以最少换乘优先，没有考虑到用户的人性需求，例如时间最优和票价最优；

（3）针对大城市，其公交地铁线路尤其复杂，数据较多，目前没有较好的优化算法来解决查询时间过长的问题。

（4）现共享单车盛行，以往的网页查询中没有考虑单车加入到公共交通出行方式中的问题。

2 改进Dijkstra算法的研究

2.1 优化思路

（1）本文将相近站点之间的换乘时间考虑进去，增加多种交通方式而非单一的公交方式。

（2）应用改进Dijkstra算法求解任意两点间的最短路径问题时，考虑站点间乘客换乘所步行的距离，根据用户需求智能分析线路，提供第三种换乘方案——少步行。

（3）传统Dijkstra算法采用邻接矩阵来存储数据，空间浪费较多，算法时间复杂度大。本文采用邻接表法存储数据，以优化存储结构；使用优先队列法排序，降低算法时间复杂度，提高算法执行效率。

（4）在传统Dijkstra算法中加入骑行方式，当步行距离大于1 000 m或者乘车少于2站时，增加单车出行方案。

2.2 改进算法描述

借用文献[2]中的内容，对改进的Dijkstra算法进行描述，其不仅能计算加权图中任意两个顶点间的最短路径，而且更易在计算机上实现，改进Dijkstra算法如下：

（1）初始化，输入起始源点s，输入目的点t。从有向加权图G=（V，E）中所有节点的集合S中读取数据，找出距起始点最近的子节点；

（2）将该点子节点距离起始点的距离值进行遍历，并求出最小值dj；

（3）将该最小值放入集合T中，把该子节点放入集合H中，重复上述步骤至集合V-S为空或找到终点。

Dijkstra算法流程如图1所示。

图1 Dijkstra算法流程图

在代码定义部分，先定义最大顶点个数max、定点个数n和边结点结构体arnode，其中vertex是和表头结点相邻的顶点编号数，weight是连接两顶点的边的权值（三种方案的weight权值不同）。其次，定义顶点结点结构体venode，其中vex是当前顶点的编号，f i rarc是与该节点相连的第一个节点组成的边值。最后，定义INF值等于0xfffff，father[a]是每个顶点的父亲节点，visited[max]用来判断起始源点s是否已经在最短路树中。noded[max]是起始源点s到其他顶点的距离，priority_queue q表示优先队列stl。

2.3 算法的程序实现

在参考文献[5]中已给出伪代码，其算法核心代码如下：

void Dijkstra（int s） //传入源顶点

{

for（int i = 1 ； i <= n ； i++）

{

d[i].id = i；

d[i].weight = INF； //设估算距离为INF

father[i] = -1； //每个顶点均无父节点

visited[i] = false； //都未找到最短路

}

d[s].weight = 0； //最短路权值为0

q.push（d[s]）； //压入队列中

while （!q.empty（） //队列空，完成操作

{

node cd = q.top（）； //取最小距离顶点

q.pop（）；

int u = cd.id；

if（visited[u]） continue ；

visited[u] = true；

arnode * p = Ver[u].f i rarc； //松弛操作

while（p != NULL）

{

int v = p->vertex；

if（!visited[v]&&d[v].w >d[u].w+p->weight）

{

d[v].w = d[u].w+p->weight；

father[v] = u；

q.push （d[v]）；

}

p = p->next；

}

相对于传统的Dijkstra算法采用稀疏矩阵进行数据存储，上述代码采用邻接表的链式存储结构[6]，使用两个数组进行存储，一个存储所求起始源点s到其他顶点的最短路值，另一个存储暂时没有排序的节点，节省存储空间，提高算法的执行效率。

3 改进算法论证与分析

3.1 算法论证实例1

选取地铁公交线路较简单的南昌市江西师范大学瑶湖校区到紫金城为例，其中X表示江西师范大学瑶湖校区，Y表示紫金城小区，A～D表示地铁1号线站点，数字1～4表示公交220站点，5～8表示公交3站点，9～11表示高铁巴士7线站点，12～15表示公交816站点，16～17表示公交1站点，18～22表示公交816站点。其中有向图中每两点间的数值从左到右表示上述站间步行的距离（km）和时间（min）。南昌站点信息有向图如图2所示。

图2 南昌站点信息（路程权值）有向图

基于大数据分析得出，平均每人步行时间为3.6 km/h，南昌市的公交时速和地铁时速分别为30 km/h和45 km/h。将路程权值改为时间权值，利用改进的Dijkstra算法可求得时间最优方案解，如图3所示。

其算法结果如下：把起点与下一节点相连的所有路线依次进行比较，从中选出最佳路径。再以最佳路径为起点，依次比较与之相连的路线，再次得到最佳路径。实例1最佳方案见表1所列。

图3 南昌站点信息（时间权值）有向图

表1 实例1最佳方案

上述三种方案都可满足单车出行的要求。

3.2 算法论证实例2

选取复杂地铁公交线路的实例北京市，以中国传媒大学到圆明园公园遗址为例，其中A表示中国传媒大学，B表示圆明园公园遗址，1～12表示快速公交2号线站点，12～18表示地铁2号线，18～25，45和54表示北京地铁4号线站点，13～17表示北京地铁10号线站点，18～25，45以及54表示地铁4号线，9和26～35表示671路公交，36～48表示地铁6号线，48和20表示地铁9号线，49～53表示公交517路，40，55～60和20表示地铁10号线。

其中相同站点出现两次表示站内换乘，例如48->48，同样将图4所示的路程权值改为时间权值。利用改进的Dijkstra算法可求得时间最优方案解，重复以上步骤，算出起点与终点的最佳路径，得出最佳方案，见表2所列。

表2 实例2最佳方案

其中，最少换乘有2种可选方案，系统优先推荐其中耗时最短和少步行的路线，时间最优和最少换乘方案步行推荐单车出行。算法时间对比见表3所列。

表3 算法时间对比

可以看出，不论简单或复杂的地铁公交网络，运用改进后的算法均能提供上述三种查询方案，并大大减少了算法运行时间，验证了方案的可行性。

图4 北京站点信息（路程权值）有向图

3.3 空间复杂度分析

传统的Dijkstra算法采用稀疏矩阵存储，数据存储量为n2，其中n是加权网络图中的节点数，这种计算方法不仅浪费时间，还占用了较大的存储空间。本文采用邻接表的链式存储结构[6]，使用两个数组进行存储，一个存储所求起始源点s到其他顶点的最短路值，另一个存储暂时没有排序的节点。最终算法空间复杂度是O（e+4n），e=2.718 281 828 459。改进的Dijkstra算法与传统算法相比，不仅节省了存储空间，更提高了算法的执行效率。

3.4 时间复杂度分析

传统Dijkstra算法中广度优先搜索法需要访问所有节点，耗时长。而改进的Dijkstra算法只需查找待排序点和堆排。运行时间主要由已标记点的邻接点集合中元素的数量决定，且该数量值小于未标记集合中的元素数量值，查找次数至多为e次。改进算法中每次调整的时间复杂度不大于满二叉树的高度log2n。整个过程一共迭代执行n次，最大运行时间是O（n（log2n+e））。因此改进的Dijkstra算法有效减少了计算次数与比较次数，降低了算法的时间复杂度。改进前后算法复杂度对比见表4所列。