摘要：隨著全球經濟的騰飛，對交通運輸的需求越來越迫切。怎樣有效地提高現有交通運輸的效率，這就是所要研究的主要問題，最優交通路徑算法。它是利用Dijkstra解決最優路徑問題，它通過分步方法求出最短路徑。最優路徑中的“優”包括很多層面，它可以是一般地理意義上的距離最短，還可以是時間最短、費用最少、線路利用率最高等多方面。但是無論哪種判斷標準，其核心實現方法都是最短路徑算法。對于交通公路來說，距離因素是最重要的，所以在論文的中，主要討論距離最短的路徑。

關鍵詞：最短路徑算法；線路利用率；子程序
中圖分類號：TP311文獻標識碼：A文章編號：1009-3044\\(2010\\)20-5574-03
The Most Optimal Path Traffic
WEI Qing
\\(Computer Science and Electronic Information Engineering Department, Heze University, Heze 274015, China\\)
Abstract: With the global economy to take off, to the transport needs of more and more pressing. How to effectively improve the efficiency of existing transport, which is the main issue to be studied, optimal traffic path algorithm. It is the optimal path using Dijkstra to solve the problem, which by-step method to find the shortest path. Optimal path in the "You" includes a lot of meaning, it not only refers to the general geographic sense, the shortest distance, but also is the shortest, least-cost, line utilization rate of the highest standards. But no matter what kind of extended criterion, the core realization is the shortest path algorithm. For road transport, the distance factor is most important, so in the paper, the main discussion of the shortest path distance.
Key words: shortest path algorithm; line use factor; subroutine
隨著地理信息產業的建立在全世界的普及，地理信息系統已深入到各行各業甚至各家各戶，成為人們生產、生活學習和工作中不可缺少的工具和助手。地理信息系統中網絡分析功能的主要目的是對交通網絡。最短路徑問題是交通網絡分析中的最基本最關鍵的問題，它對于交通運輸線路的選擇，通訊線路的建造與維護，運輸貨流的最小成本分析，城市公共交通網絡的規劃等，都有直接應用的價值。
1 最優交通路徑功能介紹
程序中設置了國內部分城市間的距離，然后對用戶選擇的兩個城市，計算出兩個城市之間的最短距離，以及連接它們的相應路線。
2 最優交通路徑程序使用算法描述
假設我們用鄰接矩陣表示所研究的圖,規定對角線元素取零值,各有向邊的元素取該邊的權值,若兩頂點間無相應方向的邊,則該元素取無窮大。此矩陣用一個（n*n）二維數組表示，無窮大元素用一個很大的有限值代替，如果得到的某路徑“長度”等于此給定的很大值，說明實際上不存在此路徑。首先引入兩個輔助向量，一個是向量dist，它的每個分量dist[i]表示當前找到的從始點V 到每個終點Vi 的最短路徑長度。另一個向量是S，S 為已找到的從V 出發的最短路徑的終點的集合，其初始值為空集。
3 最優交通路徑程序設計的實現過程
3.1 最優交通路徑程序設計的步驟
定義數據結構。
第一、用CreateUDN\\(\\)函數生成一個交通圖。
第二、用narrate\\(\\)函數進行格式輸入。
第三、用shortestpath\\(\\)生成最短路徑算法。
第四、用output函數把計算的結果格式輸出。
3.2 城市交通圖及圖的存儲類型定義
因為兩個城市間距離是互相的，所以可把圖3部分城市交通圖看作一個無向圖，把圖中的城市看作無向圖中的頂點，任意兩個頂點之間都存在聯系，無法以數據元素在存儲區中的物理位置來表示元素之間的聯系，即沒有順序存儲結構，可借助結構數組的數據類型表示元素之間的關系。
結構體的定義：
1\\) 邊的類型定義：
typedef struct ArcCell{
int adj;/*相鄰接的城市序號*/
}ArcCell; /*定義邊的類型*/
2\\) 頂點的類型定義：
typedef struct VertexType{
int number;/*城市序號*/
char city; /*城市名稱*/
}VertexType; /*定義頂點的類型*/
3\\) 圖的類型定義：
typedef struct{
VertexType vex[25];/*圖中的頂點，即為城市*/
ArcCell arcs[25][25]; /*圖中的邊，即為城市間的距離*/
int vexnum,arcnum; /*頂點數，邊數*/
}MGraph; /*定義圖的類型*/
3.3 圖的構造過程
圖的存儲結構定義完成后，開始構造圖。
1\\) 為每個城市編寫一個序號，從0開始至24。以烏魯木齊為數組的起點，依次為西寧，蘭州，呼和浩特，北京，天津，沈陽，長春，哈爾濱，大連，西安，鄭州，徐州，成都，武漢，上海，昆明，貴州，株州，南昌，福州，柳州，南寧，廣州，深圳。Creatudn\\(\\)函數根據用戶輸入的頂點數和邊數生成一個相應的交通圖，其頂點對應于城市，邊對應于城市間的直接通路，能生成一個擁有25個城市，30條公路的交通圖。具體程序段如下：
G.vexnum=v;
G.arcnum=a;
for\\(i=0;i/*下邊是城市名*/
G.vex[0].city="烏魯木齊";
G.vex[1].city="西寧";
G.vex[2].city="蘭州";
G.vex[3].city="呼和浩特";
G.vex[4].city="北京";
G.vex[5].city="天津";
G.vex[6].city="沈陽";
G.vex[7].city="長春";
G.vex[8].city="哈爾濱";
G.vex[9].city="大連";
G.vex[10].city="西安";
G.vex[11].city="鄭州";
G.vex[12].city="徐州";
G.vex[13].city="成都";
G.vex[14].city="武漢";
G.vex[15].city="上海";
G.vex[16].city="昆明";
G.vex[17].city="貴州";
G.vex[18].city="株洲";
G.vex[19].city="南昌";
G.vex[20].city="福州";
G.vex[21].city="柳州";
G.vex[22].city="南寧";
G.vex[23].city="廣州";
G.vex[24].city="深圳";
2\\) 可直接到達的城市，城市間距離是相互的，所以要對圖中對稱的邊同時付值，程序部分節選如下（G.arcs[i][j].adj表示的是序號為i的城市與序號為j的城市之間的距離）：
G.arcs[0][2].adj=G.arcs[2][0].adj=1892;
G.arcs[1][2].adj=G.arcs[2][1].adj=216;
G.arcs[2][3].adj=G.arcs[3][2].adj=1145;
G.arcs[2][10].adj=G.arcs[10][2].adj=676;
3.4 最優交通路徑函數的描述
如何求的最短路徑？可以按路徑長度增長的次序產生最短路徑：
第一、先定義v到w的權值和最短路徑集合，用帶權的鄰接鉅陣arcs表示帶權無向圖，arcs[v][w].adj表示到上的權值，若不存在，則置arcs[v][w].adj為∞（既為程序中的20000），min為找到從v出發的最短路徑的終點的集合，它的初始狀態為空集，那么從v出發到圖上其余各頂點w可能達到的最短路徑長度處值為arcs[v][w]。
第二、選擇min使min=min{arcs[v][w]}。
第三、修改以v出發到v―min上任一頂點w可達的最短路徑長度，如果Min+G.arcs[v][w].adj 第四、重復操作第一、第二共n-1次。由此求得從v到圖上其余各頂點的最短交通路徑是依據長度遞增的序列。
第五、時間復雜度：第一個for循環時間是0\\(n\\),第二個for循環共進行n-1次，
每次執行時間是0\\(n\\),所以總時間是0\\(n2\\)。
綜合上面的過程，可以發現：
1\\) 將起點插入樹中。
2\\) 找出圖中所有頂點的鄰接邊，總和最小的邊。
3\\) 重復第二步驟，直到所有的頂點都在樹中為止。
最短路徑程序如下：
void ShortestPath\\(intnum\\) /*最短路徑函數*/
{ int v,w,i,t;
int final[25];
int min;
for\\(v=0;v<25;++v\\)
{ final[v]=0;D[v]=G.arcs[num][v].adj;
for\\(w=0;w<25;++w\\) P[v][w]=0;
if\\(D[v]<20000\\) {P[v][num]=1;P[v][v]=1;}}
D[num]=0;final[num]=1;
for\\(i=0;i<25;++i\\)
{min=20000;
for\\(w=0;w<25;++w\\)
if\\(!final[w]\\)
if\\(D[w] final[v]=1;
for\\(w=0;w<25;++w\\)
if\\(!final[w]&&\\(\\(min+G.arcs[v][w].adj\\) { D[w]=min+G.arcs[v][w].adj;
for\\(t=0;t<25;t++\\) P[w][t]=P[v][t];
P[w][w]=1; }}}
4 總結
本文從空間分析的角度出發，較詳細的研究了網絡分析中最短路徑問題，以及在最短路徑基礎上的路線查詢。其特點如下：
1\\) 采用圖的結點――弧段聯合結構表示路線的相互關系，建立了網絡要素之間的拓撲結構，從而較方便的查詢交通信息及最短路徑。
2\\) 在Dijkstra算法的基礎上，用鄰接點算法來優化最短路徑問題，在一定程度上節省了存貯空間和提高了運算速度。
參考文獻：
[1] 邊馥苓.地理信息系統原理和方法[M].北京:測繪出版社,1996.
[2] 唐邦民,謝晗昕.數據結構與算法分析[M].北京:電子工業出版社,2005.
[3] 嚴蔚敏,吳偉民.數據結構[M].北京:清華大學出版社,1997.
[4] 劉家壯,王建方.網絡最優化[M].武漢:華中工學院出版社.1987.
[5] 曹麗明.圖論及其在計算機科學中的應用[M].徐州:中國礦業大學出版社,1995.
[6] 韓鵬.地理信息系統開發[M].武漢:武漢大學出版社,2004.