论文部分内容阅读
摘要：本文根据交通咨询系统中图的特点，基于Dijkstra算法，自动求取了从起始城市到目的城市的时间最短的行程安排。在算法的具体实现过程中给出了一种新的数据结构，这个数据结构使得算法结构更加简洁。
关键词：最短路径；Dijkstra算法；交通咨询系统
中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)05-11366-02
1 引言
惜时如金的现代人，希望能够事先安排好自己的旅程，以使整个旅程所耗时间最少，而且自己在整个旅程中具体乘坐几点钟的班车或航班也是很清楚的。这就使得人们要求交通咨询系统能够提供旅途时间最省路径的咨询。最短路径不仅仅指一般地理意义上的距离最短，还可引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。交通咨询系统中求取时间最省路径的核心算法是最短路径算法．经典的最短路径算法Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法。要在计算机上建立一个可以求取时间最省路径的交通咨询系统，可以采用图的结构来表示实际的交通网络。图中的顶点表示城市，边表示城市间的交通联系。我们用C#实现了这样一个交通咨询系统，该系统可以求取时间最省路径和路径最短路径，本文对系统中如何求取时间最省路径进行了阐述。
2 经典Dijkstra算法介绍
Dijkstra是一个按路径长度递增的次序产生到各个顶点的最短路径算法。Dijkstra算法的基本思路是：假设每个点都有一对标号(dj,pj)，其中dj是从起源点s到点j的最短路径的长度（我们认为从顶点到其本身的最短路径是零路，其长度等于零）；pj则是从s到j的最短路径中j点的前一点（我们常讲路径中j点的前驱节点）。求解从起源点s到点j的最短路径算法的基本过程如下：
(1)初始化。起源点设置为：① ds=0，ps为空；② 所有其他点：di=∞，pi=?；③ 标记起源点s，记k=s，其他所有点设为未标记的。
(2)检验从已标记的点k到其直接连接的未标记的点j的距离，并设置：dj=min [dj,dk+dkj]，式中，dkj是从点k到j的直接连接距离。并标记j的前驱点信息k。临时标志所求出的信息。
(3)选取下一个点。从所有临时标记的结点中，选取dj中最小的一个i：di=min [dj，所有临时标记的点j]，点i就被选为最短路径中的一点，并设为已标记的。
(4)如果所有点已标记，则算法完全退出，否则，记k=i，转到(2)再继续。
用经典Dijkstra算法求得的是从某个源点到其余各顶点的最短路径，在我们这个交通咨询系统中求的是从某个源城市到另一个目标城市的路径最短或时间最省路径，为此我们在上述经典Dijkstra算法的第(4)步中否则前可加入：或者i就为目标点j也结束算法。这样我们的算法在求得所需的路径后就可结束算法，不必求得源城市到其它所有城市的最短路径。
3 时间最省算法的设计
3.1 数据结构的设计
我们在这个交通咨询系统中用Dijkstra算法求某个源城市到某个目标城市的时间最省路径，设计一个什么样的数据结构可以简便求得这样一条路径呢?我们把我们的系统抽象在一个有向图上来实现，在求一个源城市到某个目标城市的最短路径时，我们注意到沿途所经过的城市(中间节点)的入度都是1，出度都是≥1的，根据这一点我们考虑把前一城市的出发天序数和出发时间信息保存到当前节点中来，这样我们可以大大简化具体的实现算法。在求解时间最省路径时我们设计如下两个类：
类1：
public class city
{public int id; //城市代码
public string sCityName; //城市名字
public int x; //城市坐标 X
public int y; //城市坐标 Y 绘图用，不绘图可省略
public int dist; //表示起始城市到当前城市的最短路径
public bool flag; //计算标志
public int idPreCity; //最短路径中的前趋城市节点代码
public float minTm; //表示起始城市到当前城市所需的最短时间
public float arrivalTime;//表示到当前城市的时间
public float preCityStartTime;//表示到当前城市路径中的前趋城市的出发时间
public int arrivalDay; // 表示到当前城市的天序数
public int preCityStartDay; //表示到当前城市路径中的前趋城市的出发天序数 }
类2：
public class mtNode
{ public int idCity;//表示有航班信息
public int nDistance; //表示航线距离
public int[] iTime = new int[4]; //表示航班时间信息，假设有4个航班 }
交通咨询系统中的图是一个非完备的拓扑关系图，只涉及点线不涉及面。类1是城市节点属性设置，在算法中动态生成的一些信息（如：最省时间，到达时间，到达天序数，前一城市的出发时间等）都存放在这个结构中。类2是城市间的交通联系信息的属性设置，是图节点之间的关系属性设置，我们以邻接矩阵来存储这些关系数据，邻接矩阵节点属性中矩阵的行和列隐含表示了某一线路的起点和终点城市信息。设置了上述两个类后，在程序中我们需要维护两个数组：一个数组存放城市信息（包括一些动态信息），一个数组存放城市之间的联系信息（如：cityNode cities[CITYNUMBER]; mtNode mts[CITYNUMBER*CITYNUMBER];其中的CITYNUMBER是我们这个系统中的城市数，该系统考虑了以后的可扩展性）。
3.2 时间最省算法的详细设计
根据3.1中设计的数据结构和1中给出的经典Dijkstra算法，我们设计了针对我们这个交通咨询模拟系统的时间最短路径算法。为求把算法思想表示得更清楚我们特作出该算法的PAD图如下：
4 实现
基于上述的设计，我们用C#编写程序实现了该系统（其中路径最短算法分析相同，数据结构也相同，在此略）。该系统中有关一些地图信息是从文件中读取的，这样有利于程序的扩展。该系统有很强的用户友好性，起始城市和目的城市可以在地图中用鼠标左右键选取，也可在下拉列表框中选取。计算结果在图形中显示，也在文本中输出，同时还可输出到文件保存。
该系统的初始界面如图1所示：
图1中已选择好初始城市和目的城市，我们点击时间最短按钮，就可把时间最短路径求出来，如图2示：
我们可把计算结果以文本形式显示如图3：
实现的具体代码在此就不一一列出了，有需要的同仁可直接向作者索取。本文讲述了交通咨询系统中时间最省路径求取的分析和实现，充分地从交通咨询系统中图的特点来巧妙设计数据结构，接下去的工作要更多地考虑算法改进，以更快地速度求得一条最短路径，以适应现在对这类系统的实时要求。
参考文献：
[1]乐阳，龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报，1999,24(3):209-212.
[2]Zhan F B. Three Fastest Shortest Path Algorithms on Real Road Networks. Journal of Geographic Information and Decision Analysis, 1997,1(1):69-82.
[3]严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 北京:清华大学出版社,2006.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：最短路径；Dijkstra算法；交通咨询系统
中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)05-11366-02
1 引言
惜时如金的现代人，希望能够事先安排好自己的旅程，以使整个旅程所耗时间最少，而且自己在整个旅程中具体乘坐几点钟的班车或航班也是很清楚的。这就使得人们要求交通咨询系统能够提供旅途时间最省路径的咨询。最短路径不仅仅指一般地理意义上的距离最短，还可引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。交通咨询系统中求取时间最省路径的核心算法是最短路径算法．经典的最短路径算法Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法。要在计算机上建立一个可以求取时间最省路径的交通咨询系统，可以采用图的结构来表示实际的交通网络。图中的顶点表示城市，边表示城市间的交通联系。我们用C#实现了这样一个交通咨询系统，该系统可以求取时间最省路径和路径最短路径，本文对系统中如何求取时间最省路径进行了阐述。
2 经典Dijkstra算法介绍
Dijkstra是一个按路径长度递增的次序产生到各个顶点的最短路径算法。Dijkstra算法的基本思路是：假设每个点都有一对标号(dj,pj)，其中dj是从起源点s到点j的最短路径的长度（我们认为从顶点到其本身的最短路径是零路，其长度等于零）；pj则是从s到j的最短路径中j点的前一点（我们常讲路径中j点的前驱节点）。求解从起源点s到点j的最短路径算法的基本过程如下：
(1)初始化。起源点设置为：① ds=0，ps为空；② 所有其他点：di=∞，pi=?；③ 标记起源点s，记k=s，其他所有点设为未标记的。
(2)检验从已标记的点k到其直接连接的未标记的点j的距离，并设置：dj=min [dj,dk+dkj]，式中，dkj是从点k到j的直接连接距离。并标记j的前驱点信息k。临时标志所求出的信息。
(3)选取下一个点。从所有临时标记的结点中，选取dj中最小的一个i：di=min [dj，所有临时标记的点j]，点i就被选为最短路径中的一点，并设为已标记的。
(4)如果所有点已标记，则算法完全退出，否则，记k=i，转到(2)再继续。
用经典Dijkstra算法求得的是从某个源点到其余各顶点的最短路径，在我们这个交通咨询系统中求的是从某个源城市到另一个目标城市的路径最短或时间最省路径，为此我们在上述经典Dijkstra算法的第(4)步中否则前可加入：或者i就为目标点j也结束算法。这样我们的算法在求得所需的路径后就可结束算法，不必求得源城市到其它所有城市的最短路径。
3 时间最省算法的设计
3.1 数据结构的设计
我们在这个交通咨询系统中用Dijkstra算法求某个源城市到某个目标城市的时间最省路径，设计一个什么样的数据结构可以简便求得这样一条路径呢?我们把我们的系统抽象在一个有向图上来实现，在求一个源城市到某个目标城市的最短路径时，我们注意到沿途所经过的城市(中间节点)的入度都是1，出度都是≥1的，根据这一点我们考虑把前一城市的出发天序数和出发时间信息保存到当前节点中来，这样我们可以大大简化具体的实现算法。在求解时间最省路径时我们设计如下两个类：
类1：
public class city
{public int id; //城市代码
public string sCityName; //城市名字
public int x; //城市坐标 X
public int y; //城市坐标 Y 绘图用，不绘图可省略
public int dist; //表示起始城市到当前城市的最短路径
public bool flag; //计算标志
public int idPreCity; //最短路径中的前趋城市节点代码
public float minTm; //表示起始城市到当前城市所需的最短时间
public float arrivalTime;//表示到当前城市的时间
public float preCityStartTime;//表示到当前城市路径中的前趋城市的出发时间
public int arrivalDay; // 表示到当前城市的天序数
public int preCityStartDay; //表示到当前城市路径中的前趋城市的出发天序数 }
类2：
public class mtNode
{ public int idCity;//表示有航班信息
public int nDistance; //表示航线距离
public int[] iTime = new int[4]; //表示航班时间信息，假设有4个航班 }
交通咨询系统中的图是一个非完备的拓扑关系图，只涉及点线不涉及面。类1是城市节点属性设置，在算法中动态生成的一些信息（如：最省时间，到达时间，到达天序数，前一城市的出发时间等）都存放在这个结构中。类2是城市间的交通联系信息的属性设置，是图节点之间的关系属性设置，我们以邻接矩阵来存储这些关系数据，邻接矩阵节点属性中矩阵的行和列隐含表示了某一线路的起点和终点城市信息。设置了上述两个类后，在程序中我们需要维护两个数组：一个数组存放城市信息（包括一些动态信息），一个数组存放城市之间的联系信息（如：cityNode cities[CITYNUMBER]; mtNode mts[CITYNUMBER*CITYNUMBER];其中的CITYNUMBER是我们这个系统中的城市数，该系统考虑了以后的可扩展性）。
3.2 时间最省算法的详细设计
根据3.1中设计的数据结构和1中给出的经典Dijkstra算法，我们设计了针对我们这个交通咨询模拟系统的时间最短路径算法。为求把算法思想表示得更清楚我们特作出该算法的PAD图如下：
4 实现
基于上述的设计，我们用C#编写程序实现了该系统（其中路径最短算法分析相同，数据结构也相同，在此略）。该系统中有关一些地图信息是从文件中读取的，这样有利于程序的扩展。该系统有很强的用户友好性，起始城市和目的城市可以在地图中用鼠标左右键选取，也可在下拉列表框中选取。计算结果在图形中显示，也在文本中输出，同时还可输出到文件保存。
该系统的初始界面如图1所示：
图1中已选择好初始城市和目的城市，我们点击时间最短按钮，就可把时间最短路径求出来，如图2示：
我们可把计算结果以文本形式显示如图3：
实现的具体代码在此就不一一列出了，有需要的同仁可直接向作者索取。本文讲述了交通咨询系统中时间最省路径求取的分析和实现，充分地从交通咨询系统中图的特点来巧妙设计数据结构，接下去的工作要更多地考虑算法改进，以更快地速度求得一条最短路径，以适应现在对这类系统的实时要求。
参考文献：
[1]乐阳，龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报，1999,24(3):209-212.
[2]Zhan F B. Three Fastest Shortest Path Algorithms on Real Road Networks. Journal of Geographic Information and Decision Analysis, 1997,1(1):69-82.
[3]严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 北京:清华大学出版社,2006.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。