基于城市公共自行車網(wǎng)的最短路徑搜索

朱敏

摘要：在圖的相關(guān)操作中，最短路徑是一個(gè)很重要的操作。該文根據(jù)蘇州市的城市公共自行車網(wǎng)絡(luò)越來越普及的實(shí)際情況，實(shí)現(xiàn)了一個(gè)小型的利用搜索系統(tǒng)來獲取最短路徑的應(yīng)用。該文以蘇州市吳中區(qū)某局部范圍內(nèi)的公共自行車站點(diǎn)及通路的數(shù)據(jù)為基礎(chǔ)，利用Dijkstra算法，獲取任意兩個(gè)站點(diǎn)之間的最短路徑。

關(guān)鍵詞：VB.net；公共交通搜索；最短路徑；Dijkstra 算法

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：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

本著“低碳生活，生態(tài)文明”的理念，蘇州市推出公共自行車服務(wù)，受到市民的普遍歡迎。目前，蘇州市已經(jīng)建成公共自行車站帶你2046個(gè)，每輛自行車的日平均每車租賃次數(shù)為5.1，公共自行車作為綠色環(huán)保的出行工具，正在蘇州市大量普及。隨著蘇州市內(nèi)公共自行車站點(diǎn)覆蓋范圍的不斷擴(kuò)大，站點(diǎn)數(shù)量的不斷增加，市民對站點(diǎn)之間的最短路徑的搜索需求也在凸顯。因此，開發(fā)一個(gè)實(shí)現(xiàn)公共自行車站點(diǎn)最短路徑搜索的應(yīng)用系統(tǒng)是很有必要的。獲取公共自行車通路的最短路徑，涉及到兩個(gè)方面的問題。一是公共自行車站點(diǎn)的道路建設(shè)問題，一是計(jì)算最短路徑的算法。該文開發(fā)的應(yīng)用系統(tǒng)使用Dijstra算法作為最短路徑的計(jì)算算法， 該算法是經(jīng)典的最短路徑算法，目前廣泛應(yīng)用在獲取最短路徑的問題中。

1 系統(tǒng)開發(fā)環(huán)境

VB.NET是微軟公司開發(fā)推出的最新的windows平臺的應(yīng)用程序開發(fā)環(huán)境。VB.NET作為一種面向?qū)ο蟮恼Z言，能夠高效地開發(fā)面向?qū)ο蟮膽?yīng)用程序。VB.NET具有面向?qū)ο?、支持繼承、窗體設(shè)計(jì)器含有許多新特性、以.net框架為基礎(chǔ)等特點(diǎn)。

2 公共自行車通路數(shù)據(jù)結(jié)構(gòu)

本文開發(fā)的應(yīng)用系統(tǒng)，是基于蘇州市吳中區(qū)的局部的公共自行車站點(diǎn)，所以使用數(shù)組等簡單的數(shù)據(jù)結(jié)構(gòu)存儲站點(diǎn)數(shù)據(jù)。使用一個(gè)二維數(shù)組存放站點(diǎn)之間的通路情況，若兩站點(diǎn)之間有通路，則將行車時(shí)間作為數(shù)組中對應(yīng)的值，若兩站點(diǎn)之間沒有通路，則將對應(yīng)的值定為10000。使用兩個(gè)一維數(shù)組，分別存放初始站點(diǎn)至各個(gè)站點(diǎn)的最短行車時(shí)間，以及存放標(biāo)識站點(diǎn)是否已獲取最短路徑的標(biāo)記。最后，使用一個(gè)二維數(shù)組存放從初始站點(diǎn)到各個(gè)站點(diǎn)的最短路徑所經(jīng)過的站點(diǎn)序號。具體如下：

Dim tu（，） As Integer //存放站點(diǎn)之間的通路情況；

Dim f（12， 12） As Integer //存放從初始站點(diǎn)到各個(gè)站點(diǎn)的最短路徑所經(jīng)過的站點(diǎn)序號；

Dim a（12） As Integer //存放初始站點(diǎn)至各個(gè)站點(diǎn)的最短行車時(shí)間；

Dim b（12） As Char //存放標(biāo)識站點(diǎn)是否已獲取最短路徑的標(biāo)記；

Dim start As Integer //存放初始站點(diǎn)；

Dim target As Integer //存放目標(biāo)站點(diǎn)；

3 Dijstra最短路徑算法

公共自行車站點(diǎn)的網(wǎng)絡(luò)通路可以抽象成一個(gè)帶權(quán)值的圖。圖中的各個(gè)節(jié)點(diǎn)表示站點(diǎn)，圖中的邊表示站點(diǎn)之間的通路，權(quán)值代表通路的行車耗時(shí)。本系統(tǒng)使用Dijstra最短路徑算法的基本步驟為：

1） 初始化數(shù)組a（），使其中存放從初始站點(diǎn)到各個(gè)站點(diǎn)的通路的權(quán)值。

2） 將所有的站點(diǎn)分成兩部分，一部分是已經(jīng)求出從出發(fā)點(diǎn)到該點(diǎn)的最短路徑的站點(diǎn)，一部分是尚未求出最短路徑的站點(diǎn)，在數(shù)組b（）中，分別用S和U標(biāo)記。初始化數(shù)組b（），初始站點(diǎn)的標(biāo)記為S，其余站點(diǎn)標(biāo)記為U。

3） 從所有標(biāo)記為U的站點(diǎn)中，找出權(quán)值最小的站點(diǎn)K，并把該站點(diǎn)的標(biāo)記改為S。

4） 修改其余標(biāo)記為U的站點(diǎn)的權(quán)值，修改規(guī)則為：若K的權(quán)值加上站點(diǎn)K到該站點(diǎn)通路值之和小于該站點(diǎn)的已有權(quán)值，則將該站點(diǎn)的權(quán)值修改為K的權(quán)值加上站點(diǎn)K到該站點(diǎn)通路值之和。

5） 重復(fù)第（3） 、（4） 兩步，直至所有站點(diǎn)的標(biāo)記變成S為止。

4 用戶界面層的實(shí)現(xiàn)

在本系統(tǒng)中，用戶輸入初始站點(diǎn)編號和目標(biāo)站點(diǎn)編號，即可搜索出這兩個(gè)站點(diǎn)之間的最短路徑，以及其耗時(shí)。系統(tǒng)的流程圖如下：

圖1 系統(tǒng)工作流程圖

本系統(tǒng)中，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