最短路徑分析在MapInfo中的實現

胡殿常，王晉秀

(解放軍1206地理信息中心，河北廊坊065000)

最短路徑分析在MapInfo中的實現

胡殿常，王晉秀

(解放軍1206地理信息中心，河北廊坊065000)

采用MapBasic語言，對MapInfo進行功能擴充，在MapInfo中實現最短路徑分析。程序首先完善路網表結構，增加路網拓撲所必需的字段;然后進行路網拓撲，建立拓撲關系，并在此基礎上采用Floyd算法實現最短路徑分析。

MapInfo;最短路徑分析;MapBasic;Floyd;GIS

一、引 言

近幾年，GIS在我國快速發展，并隨著計算機軟、硬件技術的不斷成熟，這一高新技術已由研究室走向實際應用領域，融入了人們的日常生活。電子導航是最重要的應用之一，其中最短路徑分析是構成電子導航的靈魂。此外，最短路徑分析在通信網絡、電力網絡等地理信息系統中也有著廣泛的應用。

MapInfo是一款桌面地理信息系統軟件，以簡單易學、性能穩定等特點，在GIS領域占有一定優勢。由于其數據結構相對簡單，無拓撲關系，因此軟件中沒有提供諸如最短路徑分析等基于拓撲關系的功能。但MapInfo提供了強大的二次開發接口，很多功能可通過二次開發解決。

MapInfo提供了3種二次開發方法:MapBasic語言、MapX組件和OLE技術。MapX和OLE適合開發獨立的應用系統，而MapBasic比較適合MapInfo功能擴展編程。MapBasic是MapInfo自帶的二次開發語言，是一種類似Basic的解釋性語言，利用Map-Basic編程生成的*.mbx文件可在MapInfo軟件平臺上運行。本文主要介紹采用 MapBasic語言在MapInfo中實現最短路徑分析的方法。

二、完善表結構

在MapInfo中，路網或其他網絡都以“線”的方式表現。每條線有“起點”和“終點”，統稱“端點”。線與線首尾相連，構成路網，連接處稱為“頂點”或“節點”。然而，路段編號(ID)、路段起止點、路段長度等屬性，并沒有被記錄。因此，首先要完善表結構，增加字段，記錄拓撲信息。

增加的字段有 LineID、Fnode、Tnode、Length、Selected，分別記錄路段編號、道路起點號、道路終點號、路段長度(m)和是否為選出的路段(計算結果圖形顯示時用)。主要程序片段為

Alter Table表名 (Add LineID Integer，Fnode Integer，Tnode Integer，Length float，Selected Logical)Interactive

三、建立拓撲關系

建立拓撲關系，主要需完成3項工作:給每個路段編號;計算各路段長度;計算各路段的連接關系。前兩項可簡單計算賦值，第3項的算法核心是:先選定任一路段;然后尋找所有與該路段起點相連的路段，將相連處各路段端點(路段起點或終點)賦相同編號;路段終點作相同運算。遍歷所有路段，作以上相同運算。具體算法如下:

1)針對路網表，生成查詢表RoadNet。該表中，計算出路網中各路段的起點坐標(Xf，Yf)和終點坐標(Xt，Yt)，并將各路段起止點編號賦初值0(Fnode=0、Tnode=0)。

2)i=0。

3)查找RoadNet中第一個路段。

4)如果被查到的路段起點編號不為0，說明已賦過值，執行步驟5);如果起點編號等于0，i=i+ 1，Fnode=i，即該頂點編號為i。

在RoadNet其他路段中查找起點與i點坐標值相同的路段，給起點賦相同號(Fnode=i)。

在RoadNet其他路段中查找終點與i點坐標值相同的路段，給終點賦相同號(Tnode=i)。

5)如果被查到的路段終點編號不為0，說明已賦過值，執行步驟6);如果終點編號等于0，i=i+ 1，Tnode=i，即該頂點編號為i。

在RoadNet其他路段中查找起點與i點坐標值相同的路段，給起點賦相同號(Fnode=i)。

在RoadNet其他路段中查找終點與i點坐標值相同的路段，給終點賦相同號(Tnode=i)。

6)找到RoadNet中下一個路段，重復步驟4)、步驟5)。

7)遍歷所有路段，結束。

程序片段如下

采用相似的算法，計算與上路段終點相連的路段。遍歷全部路段，結束。

四、最短路徑計算

迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法，是解決最短路徑問題的經典算法。Dijkstra算法又稱為單源最短路徑，是從一個頂點出發，求該頂點至所有可到達頂點的最短路徑;Floyd算法可以計算出所有頂點之間的最短路徑，計算結果為兩個矩陣，一個是任意兩個頂點之間的最短距離;另一個是任意兩點之間的最短路徑。很顯然，Floyd算法時間復雜度要高。但一般情況下，路網不會在短時間內更新，路網拓撲關系也相對固定，所以可采用Floyd算法，將計算結果矩陣以文件的形式保存，在最短路徑分析時，隨時調用，不再重復計算，這樣可大幅提高效率。MapInfo平臺上比較適合采用這種方法。該算法簡捷，這里不再介紹，但在算法實現中有兩點需要說明。

1.二維數組

在MapBasic語言支持的數據類型中，包含一維數組，不包含二維數組。但Floyd算法的鄰接矩陣需要用二維數組存儲、運算，因此，在程序中需要用一維數組實現二維數組功能。程序片段如下

要訪問二維數組G(m，n)時，采用G(a(m，n))的方式調用，這樣就實現了用一維數組替代二維數組。

2.計算結果的展示

在MapInfo中，計算結果要以圖形(可視化)的方式表現，因為圖形能更好地識別和解釋，達到所見即所得的效果。為方便處理，在路網表中，增加了Selected字段，最短路徑分析時，將最短路徑所包含路段的Selected值賦為1，最后在路網表中查找Selected=1即可。程序如下

五、效果展示

1)啟動MapInfo，打開或新建一個路網表。

2)運行最短路徑分析程序，MapInfo中增加了“最短路徑分析”菜單，如圖1所示。

圖1 程序運行界面

3)依次點擊“最短路徑分析”、“路網拓撲”，進行路網拓撲(每個路網只進行一次路網拓撲即可)。

4)依次點擊“最短路徑分析”、“查找最短路徑”，選取最短路徑分析工具，在圖中起點處按下鼠標左鍵，移動到終點處松開鼠標，即可顯示出起點至終點的最短路徑，如圖2、圖3所示。

圖2 定義最短路徑起止點

六、結束語

最短路徑分析是GIS的重要組成部分，有著廣泛的應用。本文提供了一種在MapInfo中實現這一功能的算法。通過實際驗證，該方法界面友好、操作簡捷、運算速度快、計算結果準確、性能穩定，有一定的實用價值。

圖3 最短路徑分析結果

［1］ 沙宗堯，邊馥苓.單源最短路徑算法的圖示教學設計與實踐［J］.測繪通報，2010(4):58-61.

［2］ 彭波.數據結構［M］.北京:清華大學出版社，2002.

［3］ 張劍平，任福繼，葉榮華，等.地理信息系統與MapInfo應用［M］.北京:科學出版社，1999.

［4］ 李勝樂，陸遠忠，車時.MapInfo地理信息系統二次開發實例［M］.北京:電子工業出版社，2004.

［5］ 王曉東，趙全磊，吳建民.MapBasic在MapInfo功能擴展中的應用［J］.測繪通報，2007(8):51-54.

［6］ 陳繼山，須鼎興.使用Shape文件進行最短路徑的分析與跟蹤［J］.測繪通報，2004(12):8-10.

［7］ 張虎，施一民.基于MapX的公安110報警系統的設計與實現［J］.測繪通報，2004(9):23-25，39.

［8］ 司連法，王文靜.快速Dijkstra最短路徑優化算法的實現［J］.測繪通報，2005(8):15-18.

［9］ 夏松，韓用順.GIS中最短路徑算法的改進實現［J］.測繪通報，2004(9):40-42.

Realization of the Shortest Path Analysis in MapInfo

HU Dianchang，WANG Jinxiu

0494-0911(2012)06-0087-03

P208

B

2011-12-02

胡殿常(1968—)，男，河北淶水人，工程師，主要從事GIS工作。