基于Dijkstra算法的地铁出行路线规划系统的设计与实现
作者： 马静 刘江岳
摘要：城市地铁已经成为许多居民出行的首选交通工具，但在一些大城市中，复杂庞大的地铁网络给出行者的线路选择和换乘带来了许多不便[1]。为了解决在日趋复杂的地铁网中找出最优路径这一问题，文章介绍的项目基于改进的Dijkstra算法，充分考虑了用户需求，设计了地铁出行线路规划系统，实现了多种路线规划模式，能够科学、高效地规划出最优路线。
关键词：改进Dijkstra算法;轨道交通;地铁;路线规划;最优路线
中图分类号：G434 文献标识码：A
文章编号：1009-3044（2022）13-0058-05
1 引言
最短路径问题在计算机科学、运筹学、地理信息科学等领域中是一个研究热点，并占有极其重要的地位[2]。随着经济的发展，越来越多的城市建设了地铁作为缓解交通压力的重要公共交通设施。但是，对于外来出行者来说，面对自己不熟悉的城市和复杂的城市地铁线路网，乘坐地铁会是一个难题;对于城市的本地居民来说，如何选择最佳的地铁乘车方案来节约宝贵的时间资源也是一个难题。明确地指引乘客乘车，有效地疏导客流在地铁的日常运营中是十分重要的。在大城市地铁线路网络庞大复杂的情况下，解决上述问题的关键在于如何根据用户的需求，快速且明确地指引乘客选择最佳出行线路[3]，因此在地铁出行路线规划的情景下研究最短路径算法是非常有必要的。本研究基于改进的Dijkstra算法，设计并实现了能在多种情形下查询地铁最优路线的地铁出行路线规划系统。
2 地铁出行路线规划软件功能需求与可行性分析
2.1 功能需求分析
现在国内市场上不乏出行路线规划软件，它们有的是针对某一个城市的地铁路线的，有的地铁、公交等多种公共交通工具。其中它们多数为移动端应用或网页，它们几乎都包含了以下相似的基本模块：1）地铁线路图：该模块提供各个线路的信息，方便乘客对单条线路进行研究、查询，同时提供高清晰的地铁线路图以及线路图的放大缩小功能[4];2）乘车查询功能：乘车查询功能要求在众多可行路线方案中默认提供到达目的地的最优路线方案，并将查询结果以多媒体的方式呈现，操作程序需简洁明了易上手[4]。该功能还包括丰富多样的站点输入方式，多种线路方案的选择。
2.2 可行性分析
1）硬件可行性分析：硬件配置需求：计算机选型为配备触摸屏的一体机，具有网络接口、麦克风和音响设备。CPU至少为1.8GHz Intel处理器，内存至少为1GB，硬盘具有30MB以上空余。其安装的操作系统最低为64位的Windows 7系统，并且.Net framework的版本最低为4.5.1。
2）软件可行性分析：地铁出行路线规划系统的后台数据，即站点数、站点名称、站点坐标、地铁线路及其包含的各个站点等信息存储于外部txt格式文件中，程序将按行从中读取数据。这样的外部存储方式使得本系统有很高的灵活性和扩展性，用户可以自定义扩充新的地铁线路图，让程序为用户提供个性化的路线规划服务。其中地铁站点坐标取自于地铁线路图片上站点的x，y坐标。
数据存储方式如表1所示。
文件名：城市名英文-subway.txt
该系统的软件程序用C++编写而成，由GUI界面、程序算法、后台数据三个部分组成，程序结构如图1所示。
该系统的前端包含语音输入功能，包含路线查询结果的语音播放功能，该功能调用了科大讯飞智能语音平台，能够在线使用语音输入和语音播放，界面支持多种语言。如图2所示，前端界面显示了高清地铁地图，操作方式为手持触屏的方式，可直接在地图上通过单击站点的方式设置起点与终点;可移动、放大、缩小地图;具有语音输入、语音播放的按钮;当前版本有三种路径规划方式可选，路线规划结果能够详细地列在输出框内，同时地图上也会直观地用标记出规划好的最佳路线。
系统的程序算法部分为改进的迪杰斯特拉算法，提供少停站优先、少换乘优先、周游一圈这三个模式，适应用户的多样化需求。
系统的后台数据为扩展文件，可从本地文件中读取地铁路线信息，可从中央服务器动态获取地铁路线信息。
3 Dijkstra算法简介
“最短路径算法”用于解决最短路径问题，其原理为：首先在路线拓扑图中找出地点作为结点，其次将节点编号并计算出所有结点间的最短路径，最后查找线路拓扑中两个目标结点的最短路径[5]。目前用于解决最短路径问题的比较成熟的算法有Dijkstra算法、A-Star 算法、Bellman-Ford算法和Floyd算法等[2，5]。四种最短路径算法的优缺点比较如表2所示。
其中，Dijkstra 算法由荷兰计算机科学家狄克斯特拉于1959 年提出，是在实际中应用最多的具有代表性的最短路径算法[3]。该算法针对具有非负权值的图。它采用标记法按照路径长度递增的顺序寻找最短路径，然后通过对路径长度迭代得到从源点到其他各目标节点的最短路径[7]。
Dijkstra算法的基本思想是：
1）设置两个节点的集合S和T，集合S是已经标记节点集，表示已经找到最短路径的节点，集合T是未标记节点集合，表示未找到最短路径的节点[7]。
2）初始状态时，集合S中只包含源点Vo[7]。
3）不断从未标记节点集合T中选取到节点Vo路径长度最短的节点Vj加入集合S中，集合S每加入一个新的节点Vj都要比较计算更新源点Vo到集合T中剩余各节点的最短路径长度值。不断重复此过程，直到集合T的节点全部加入集合S[7]。
为了解决Dijkstra算法的时间复杂度较高的缺点，以及为了满足遍历图中所有的点这一需要，本系统做了以下改进：
1）系统使用C++语言编写，通过C++程序运行的高效性的特点来弥补Dijkstra算法较高的时间复杂度。
2）拓展Dijkstra算法的思路，从解决两点之间最短路径的问题拓展到解决遍历图中的所有点的问题。遍历地图中所有站点的基本思路为，首先预处理任意两站点间的最短距离，然后每次选择一个尚未走过的站点，从当前点以最短路径走到选中的这个尚未走过的站点。在选站点时需要注意在当前站点和选中站点之间不能有其他的未选站点。
4 软件功能实现方案
综合以上分析，本系统采用Dijkstra算法进行可靠的路径规划运算，利用C++语言编程实现提高程序运行效率，弥补Dijkstra算法时间复杂度较高的缺陷，并且根据出行者乘坐地铁时的特殊情况进行规划模式上的优化改进。
本系统还增添了多媒体接口，用户能够在线使用语音输入和语音播放的功能。该语音功能采用了业界领先的科大讯飞智能语音平台。
1）语音功能技术难点分析
语音功能部分分为三个模块：讯飞云模块、语音录入模块、语音播放模块。
讯飞开放平台是开放的智能交互技术服务平台，提供了语音识别、声纹识别、自然语言处理等多项服务，让应用产品具备 “听说读写”的功能[8]。
在讯飞云模块，首先通过引入讯飞SDK的lib文件来间接调用语音函数：
#ifdef _WIN64
#pragma comment（lib，"../libs/msc_x64.lib"） //x64
#else
#pragma comment（lib，"../libs/msc.lib"） //x86
#endif
然后include以下几个头文件：
#include "qisr.h"
#include "qtts.h"
#include "msp_cmn.h"
#include "msp_errors.h"
SoundPlayer^ player = （gcnew SoundPlayer（text））;//音频播放器
player->SoundLocation = text;
player->Load（）;
player->Play（）;
m_soundFormat.cbSize = 0;
waveInOpen（&m_hWaveIn， WAVE_MAPPER， &m_soundFormat， （DWORD_PTR）（waveInProc）， 0， CALLBACK_FUNCTION）;
在语音录入模块，首先采集PCM音频流，再将其封装为wav格式的音频。该模块使用了回调函数的方法：
该模块采集音频的格式为：
在语音播放模块，直接使用了System：：Media命名空间下的类SoundPlayer：
memset（&m_soundFormat， 0， sizeof（m_soundFormat））; //设置声音格式
m_soundFormat.wFormatTag = WAVE_FORMAT_PCM; //声音格式为裸流PCM
m_soundFormat.nChannels = 1; //采样声道数
m_soundFormat.nSamplesPerSec = 22050; //采样率 22050次/秒
m_soundFormat.nAvgBytesPerSec = 22050 * 1 * 16 / 8; //每秒的数据率
m_soundFormat.nBlockAlign = 1 * 16 / 8; //一个块的大小
m_soundFormat.wBitsPerSample = 16; //采样比特
m_soundFormat.cbSize = 0;
2）路径规划功能
本地铁路径规划系统有三种路径规划方式，分别是少换乘、少停站和周游一圈。
实现这三种功能的具体步骤是：
第一步：把一条地铁线路上相邻两站点之间的边设为二元组，并且这两个站点之间用（0，1）的边相连。
第二步：把n条地铁线路交叉产生的一个站点看作是n个位置重合的站点，并且这些站点之间用（1，0）的边相连。
第三步：选择“少换乘”模式时，以整个二元组为键，进行Dijkstra计算，得出起点与终点间换乘次数最少的最优路径;选择“少停站”模式时，以二元组的第二元为键，进行Dijkstra计算，得出起点与终点之间站点数量最少的最优路径。
选择“周游一圈”模式时，首先预处理任意两点间的最短距离，然后每次选择一个尚未走过的点，从当前点以最短路径走到选中的这个尚未走过的点。在选点时需要注意在当前点和选中点之间不能有其他的未选点。
少停站规划模式的实现代码：
int do_lessstop （std：：string s， std：：string t） {
//如果没有设置起点或没有设置终点，直接返回1，不继续执行少停站的算法
if （this->mp.find（s） == this->mp.end（） || this->mp.find（t） == this->mp.end（））
{
return 1;
}
//如果设置了起点和终点，继续执行少停站的算法