摘 要： 確定兩點之間最短路徑，通常要求該路徑滿足兩點之間的權之和最小。為此采用層次遍歷圖的思想，設計了一種新的結構存放路徑選擇信息，找到一種確定這種最短路徑的算法，并給出了算法描述以及實例。
關鍵詞： 鄰接表；邊鏈表；層次遍歷圖;隊列；最短路徑
在實際生活中常常會遇到求最短路徑問題，如：從Ａ地到Ｂ地有若干條路可選，每條邊上都標有象征某種意義的權值。有人選擇路徑的方法是希望總路徑的權之和最小；有人選擇中轉次數最少；而還有人希望在中轉次數最少的條件下盡量權之和最小。確定權之和最小的最短路徑算法目前國內外公認較好的是Dijkstra算法和Floyed算法，這兩種算法已被廣泛用于生活中各個領域，如：網絡尋優、道路交通等。但這些算法都只單純地考慮路徑中權之和達到最小,而并未考慮路徑中邊數能否也最少。而在目前高科技迅猛發展的經濟時代，人們在選擇出行方案時可能會更加注重降低因中轉而產生的精力和時間的消耗而不會過多在意為此多出的花費。因此，許多情況下出行的人們會考慮中轉次數盡量少，然后在相同的中轉次數下優先選擇花錢最少的路徑作為選擇方案。
本文提出了一種確定兩個頂點之間經過的邊數最少且相同邊數前提下權值之和最小的最短路徑的一種算法。在本算法中，采用鄰接表存儲結構存儲原始圖，在層次遍歷法的思想遍歷圖的基礎上進行了修改，設計了一種新的結點結構存放路徑選擇中的信息。當遍歷到終點結點出現時，終止遍歷過程，然后在目標結構中從該終點開始按指定的指針域層層向上搜索并輸出經過的每一個結點序號直到指針為空為止。輸出的序列就是要找的最短路徑。
1 數據結構的設計及算法
設有n個頂點的一個無向圖，圖中每條邊都標有代表某種意義的權值，現求從頂點i到頂點j的邊數最少且權值也最小的最短路徑。
1.１ 數據結構的設計
(1) 采用鄰接表作為原圖的存儲結構
其中的表頭結點vnode中存放頂點信息如：城市名稱(cityname)，對應頂點的序號(verindex)以及指向該頂點的邊鏈表的頭指針域（firstarc），如圖1所示。邊鏈表結點node中存放頂點的序號(verindex)、表頭結點到該頂點的邊上的權值(weight)以及指向與表頭頂點鄰接的下一個頂點的指針域（nextarc），如圖2所示。
C語言描述如下：
typedef struct node
{ int adjindex ;
int weight ;
struct node *nextarc ;
} Node ;
typedef struct vnode
{char cityname[20];
int verindex;
struct node *firstarc;
}Vnode ;
n個頂點圖的鄰接表就定義為：vnode g[n+1];其中下標為０的元素不用。
(２) 存放路徑信息的結點結構BT
該結構中的頂點有4個域,如圖3所示。
C語言描述為：
typedef struct bt
{struct bt *parent ,*brother ,*first ;
int data ;
}BT ;
其中：
*parent：記錄該結點被確定之前的最短路徑上的前一個結點，稱之為該結點的雙親。
*brother：記錄該結點所在的邊鏈表中下一個未被訪問過的頂點。
*first：記錄該結點的邊鏈表中第一個未被訪問的頂點序號。
data：記錄該結點序號。
(３)建立一個ＢＴ類的長度為n+1隊列q并初始化為空隊。
(４) 建立一個整型一維數組visited[n+1]，用來存放每個頂點是否已被訪問過的標志，未被訪問其對應元素值為０，否則為１，因此初始化該數組全部為０。
1.２ 算法
以交通問題為例，確定從城市Ａ（對應序號為i）到城市Ｂ（對應號為j）經過的邊數最少且相同邊數條件下權之和也最小的最短路徑。
算法描述中用到的變量聲明約定如下：
Node *p,*q;
BT *t ,*r ,*u ,*q[n+1] ;
Vnode g[n+1] ;
int visited[n+1]={0}, i, j, w, k;
(1) 建立鄰接表，為了確保找到的邊數最少的路徑也一定是相同邊數下權值之和最小的一條，故要求每個頂點的邊鏈表中的權值(weight)都是按從小到大的順序連接起來的。為此，在算法中先將輸入的所有邊按權值進行降序排列，然后在建立圖的鄰接表時，依次考查每一條邊，將該邊的起點和終點分別以頭插法插入到相應終點和起點的邊鏈表中。
(2) 從頂點i開始，申請一個ＢＴ類的結點t，其中t->parent＝NULL，t->brother=NULL，t->first=NULL，t->data=i，visited[i]=1，r=t，并且將t結點加入q隊列。
(3)若q隊列未空，將隊首元素出隊,即u=q[++front]，并獲取u->data在鄰接表中的邊鏈表的頭指針，即p=g[u->data]->firstarc，設置一個標志變量k=1（當k為１時，說明剛出隊的隊首結點u的邊鏈表中還沒有一個未被訪問的結點加入到目標路徑中）。
一個結點剛出隊時，該結點的邊鏈表中肯定還沒有一個結點被加入到目標路徑中，因此該結點將作為它的邊鏈表中的結點的雙親結點。
(4) 若p非空（即雙親結點邊鏈表還未訪問完），則獲取w=p->adindex，并按序執行進行如下三種情況：
①若p指向的結點未被訪問過，即：visited[w]=0，且k=1，則說明結點w是雙親結點的邊鏈表中第一個未被訪問過的結點，故w應該加入目標結構中成為雙親u的first。因此為 w申請一個ＢＴ類的結點空間t，此時，t為u的first，t的parent為u，即：u->first=t，t->parent=u，t->data=w，t->brother=NULL，t->first=NULL，r=t，并將t入q 隊列。
②若p指向的結點未被訪問過，且k=0， 則說明w不是雙親結點的邊鏈表中第一個未被訪問過的結點，故w應作為前一個未被訪問結點t的brother而加入到目標結構中。因此申請一個BT類結點空間t，t只能作為r的兄弟連接，t的雙親仍為u,即：r->brother=t，t->parent=u，t->first=NULL，t->brother=NULL，t->data=w，r=t。
③若p指向的結點w未被訪問過，則置visited[w]為1且k為0。此時再做如下判斷：
若t->data＝＝j，說明了剛加入目標結構中的結點就是終點，最短路徑已經找到。因此從t開始按雙親域層層向上搜索目標結構并一一輸出每個結點的data域，直到結點為空為止，輸出的就是要找的路徑，結束本算法。
若t->data!=j說明剛加入目標結構的結點還不是終點，則繼續考慮邊鏈表的下一個結點，即p=p->nextarc，轉④繼續。
④若p指向的結點w已被訪問過,則p=p->nextarc，轉4）繼續。
(5) 若p為空，說明雙親u的邊鏈表已全部經遍歷，應該從隊列出取出一個新的結點繼續考查。故轉③繼續。 (6) 若q已空，則說明從i到j無路徑，算法結束。
2 實例
以下以一個交通圖為例,求任意兩點之間的邊數最少且權之和也最小的最短路徑。如圖4所示。
在該圖中各頂點分別代表不同的城市名，兩點之間有邊相連代表兩個頂點鄰接，邊上的權值代表兩點之間乘車的費用。
問題:尋找從1~５的邊數最少且權之和最小的路徑。
圖4所建的鄰接表如圖5所示。
按照上述算法所得的目標結構圖如圖6所示。
從終點5開始按praent域層層向上搜索直到結點為
空為止，得一結點序列5，4，2，1，因此，1->2->4->5就是該問題要找的從結點1到結點5的最短路徑，其權之和6也是相同邊數的路徑中權之和最小的一個。
本文采用了圖的鄰接表結構以及層次遍歷思想，給出了一種確定任意兩點之間中轉邊數最少且權值最小的最短路徑的算法，并給出了一個實例。這種算法并不是最理想的，但至少是一種有效的實現方法，還有待于進一步優化和改進。
參考文獻
[１] 張群哲．數據結構（C語言版）[M].西安:西安電子科技出版社，2008：131-140.
[２] 安訓國,劉俞．數據結構（第三版）.[M]大連:大連理工大學出版社，2003：136-160.