基于城市公共自行车网的最短路径搜索

朱敏

摘要：在图的相关操作中，最短路径是一个很重要的操作。该文根据苏州市的城市公共自行车网络越来越普及的实际情况，实现了一个小型的利用搜索系统来获取最短路径的应用。该文以苏州市吴中区某局部范围内的公共自行车站点及通路的数据为基础，利用Dijkstra算法，获取任意两个站点之间的最短路径。

关键词：VB.net；公共交通搜索；最短路径；Dijkstra 算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）19-4593-02

The Shortest Path Searching Based on City Public Bicycle Network

ZHU Min

（Suzhou Vocational Universtiy，Suzhou 215104，China）

Abstract： In the related operations in the graph， the shortest path is a very important operation. In this paper， according to the actual situation of city public bicyclenetwork of Suzhou city is becoming more and more popular， to achieve a small use of search system to obtain the shortest path to the application.This paper is based on the public bicycle station and Suzhou city Wuzhong District a local path within the scope of the data， using the Dijkstra algorithm，the shortest path between any two sites.

Key words： VB.net； public traffic search； shortest path； Dijkstra algorithm

本著“低碳生活，生态文明”的理念，苏州市推出公共自行车服务，受到市民的普遍欢迎。目前，苏州市已经建成公共自行车站带你2046个，每辆自行车的日平均每车租赁次数为5.1，公共自行车作为绿色环保的出行工具，正在苏州市大量普及。随着苏州市内公共自行车站点覆盖范围的不断扩大，站点数量的不断增加，市民对站点之间的最短路径的搜索需求也在凸显。因此，开发一个实现公共自行车站点最短路径搜索的应用系统是很有必要的。获取公共自行车通路的最短路径，涉及到两个方面的问题。一是公共自行车站点的道路建设问题，一是计算最短路径的算法。该文开发的应用系统使用Dijstra算法作为最短路径的计算算法， 该算法是经典的最短路径算法，目前广泛应用在获取最短路径的问题中。

1 系统开发环境

VB.NET是微软公司开发推出的最新的windows平台的应用程序开发环境。VB.NET作为一种面向对象的语言，能够高效地开发面向对象的应用程序。VB.NET具有面向对象、支持继承、窗体设计器含有许多新特性、以.net框架为基础等特点。

2 公共自行车通路数据结构

本文开发的应用系统，是基于苏州市吴中区的局部的公共自行车站点，所以使用数组等简单的数据结构存储站点数据。使用一个二维数组存放站点之间的通路情况，若两站点之间有通路，则将行车时间作为数组中对应的值，若两站点之间没有通路，则将对应的值定为10000。使用两个一维数组，分别存放初始站点至各个站点的最短行车时间，以及存放标识站点是否已获取最短路径的标记。最后，使用一个二维数组存放从初始站点到各个站点的最短路径所经过的站点序号。具体如下：

Dim tu（，） As Integer //存放站点之间的通路情况；

Dim f（12， 12） As Integer //存放从初始站点到各个站点的最短路径所经过的站点序号；

Dim a（12） As Integer //存放初始站点至各个站点的最短行车时间；

Dim b（12） As Char //存放标识站点是否已获取最短路径的标记；

Dim start As Integer //存放初始站点；

Dim target As Integer //存放目标站点；

3 Dijstra最短路径算法

公共自行车站点的网络通路可以抽象成一个带权值的图。图中的各个节点表示站点，图中的边表示站点之间的通路，权值代表通路的行车耗时。本系统使用Dijstra最短路径算法的基本步骤为：

1） 初始化数组a（），使其中存放从初始站点到各个站点的通路的权值。

2） 将所有的站点分成两部分，一部分是已经求出从出发点到该点的最短路径的站点，一部分是尚未求出最短路径的站点，在数组b（）中，分别用S和U标记。初始化数组b（），初始站点的标记为S，其余站点标记为U。

3） 从所有标记为U的站点中，找出权值最小的站点K，并把该站点的标记改为S。

4） 修改其余标记为U的站点的权值，修改规则为：若K的权值加上站点K到该站点通路值之和小于该站点的已有权值，则将该站点的权值修改为K的权值加上站点K到该站点通路值之和。

5） 重复第（3） 、（4） 两步，直至所有站点的标记变成S为止。

4 用户界面层的实现

在本系统中，用户输入初始站点编号和目标站点编号，即可搜索出这两个站点之间的最短路径，以及其耗时。系统的流程图如下：

图1 系统工作流程图

本系统中，Dijstra算法核心代码如下：

For i = 0 To 11

If b（i） = "U" Then

If a（k） + tu（k， i） < a（i） Then

a（i） = a（k） + tu（k， i）

For j = 0 To 11

If f（i， j） = -1 Then

f（i， j） = k

Exit For

End If

Next

End If

End If

Next