摘  要： 確定兩點(diǎn)之間最短路徑，通常要求該路徑滿足兩點(diǎn)之間的權(quán)之和最小。為此采用層次遍歷圖的思想，設(shè)計(jì)了一種新的結(jié)構(gòu)存放路徑選擇信息，找到一種確定這種最短路徑的算法，并給出了算法描述以及實(shí)例。
關(guān)鍵詞： 鄰接表；邊鏈表；層次遍歷圖;隊(duì)列；最短路徑

    在實(shí)際生活中常常會(huì)遇到求最短路徑問題，如：從Ａ地到Ｂ地有若干條路可選，每條邊上都標(biāo)有象征某種意義的權(quán)值。有人選擇路徑的方法是希望總路徑的權(quán)之和最??；有人選擇中轉(zhuǎn)次數(shù)最少；而還有人希望在中轉(zhuǎn)次數(shù)最少的條件下盡量權(quán)之和最小。確定權(quán)之和最小的最短路徑算法目前國內(nèi)外公認(rèn)較好的是Dijkstra算法和Floyed算法，這兩種算法已被廣泛用于生活中各個(gè)領(lǐng)域，如：網(wǎng)絡(luò)尋優(yōu)、道路交通等。但這些算法都只單純地考慮路徑中權(quán)之和達(dá)到最小,而并未考慮路徑中邊數(shù)能否也最少。而在目前高科技迅猛發(fā)展的經(jīng)濟(jì)時(shí)代，人們在選擇出行方案時(shí)可能會(huì)更加注重降低因中轉(zhuǎn)而產(chǎn)生的精力和時(shí)間的消耗而不會(huì)過多在意為此多出的花費(fèi)。因此，許多情況下出行的人們會(huì)考慮中轉(zhuǎn)次數(shù)盡量少，然后在相同的中轉(zhuǎn)次數(shù)下優(yōu)先選擇花錢最少的路徑作為選擇方案。
    本文提出了一種確定兩個(gè)頂點(diǎn)之間經(jīng)過的邊數(shù)最少且相同邊數(shù)前提下權(quán)值之和最小的最短路徑的一種算法。在本算法中，采用鄰接表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)原始圖，在層次遍歷法的思想遍歷圖的基礎(chǔ)上進(jìn)行了修改，設(shè)計(jì)了一種新的結(jié)點(diǎn)結(jié)構(gòu)存放路徑選擇中的信息。當(dāng)遍歷到終點(diǎn)結(jié)點(diǎn)出現(xiàn)時(shí)，終止遍歷過程，然后在目標(biāo)結(jié)構(gòu)中從該終點(diǎn)開始按指定的指針域?qū)訉酉蛏纤阉鞑⑤敵鼋?jīng)過的每一個(gè)結(jié)點(diǎn)序號直到指針為空為止。輸出的序列就是要找的最短路徑。
1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及算法
    設(shè)有n個(gè)頂點(diǎn)的一個(gè)無向圖，圖中每條邊都標(biāo)有代表某種意義的權(quán)值，現(xiàn)求從頂點(diǎn)i到頂點(diǎn)j的邊數(shù)最少且權(quán)值也最小的最短路徑。
1.１ 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)
    (1) 采用鄰接表作為原圖的存儲(chǔ)結(jié)構(gòu)
    其中的表頭結(jié)點(diǎn)vnode中存放頂點(diǎn)信息如：城市名稱(cityname)，對應(yīng)頂點(diǎn)的序號(verindex)以及指向該頂點(diǎn)的邊鏈表的頭指針域（firstarc），如圖1所示。邊鏈表結(jié)點(diǎn)node中存放頂點(diǎn)的序號(verindex)、表頭結(jié)點(diǎn)到該頂點(diǎn)的邊上的權(quán)值(weight)以及指向與表頭頂點(diǎn)鄰接的下一個(gè)頂點(diǎn)的指針域（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個(gè)頂點(diǎn)圖的鄰接表就定義為：vnode  g[n+1];其中下標(biāo)為０的元素不用。
    (２) 存放路徑信息的結(jié)點(diǎn)結(jié)構(gòu)BT
      該結(jié)構(gòu)中的頂點(diǎn)有4個(gè)域,如圖3所示。

       C語言描述為：
       typedef struct bt
       {struct  bt  *parent ,*brother ,*first ;
           int  data ;
       }BT ;
    其中：
    *parent：記錄該結(jié)點(diǎn)被確定之前的最短路徑上的前一個(gè)結(jié)點(diǎn)，稱之為該結(jié)點(diǎn)的雙親。
    *brother：記錄該結(jié)點(diǎn)所在的邊鏈表中下一個(gè)未被訪問過的頂點(diǎn)。
    *first：記錄該結(jié)點(diǎn)的邊鏈表中第一個(gè)未被訪問的頂點(diǎn)序號。
    data：記錄該結(jié)點(diǎn)序號。
    (３)建立一個(gè)ＢＴ類的長度為n+1隊(duì)列q并初始化為空隊(duì)。
    (４) 建立一個(gè)整型一維數(shù)組visited[n+1]，用來存放每個(gè)頂點(diǎn)是否已被訪問過的標(biāo)志，未被訪問其對應(yīng)元素值為０，否則為１，因此初始化該數(shù)組全部為０。
1.２ 算法
    以交通問題為例，確定從城市Ａ（對應(yīng)序號為i）到城市Ｂ（對應(yīng)號為j）經(jīng)過的邊數(shù)最少且相同邊數(shù)條件下權(quán)之和也最小的最短路徑。
    算法描述中用到的變量聲明約定如下：
       Node *p,*q;
    BT  *t ,*r ,*u ,*q[n+1] ;
       Vnode  g[n+1] ;
       int  visited[n+1]={0}, i, j, w, k;
    (1) 建立鄰接表，為了確保找到的邊數(shù)最少的路徑也一定是相同邊數(shù)下權(quán)值之和最小的一條，故要求每個(gè)頂點(diǎn)的邊鏈表中的權(quán)值(weight)都是按從小到大的順序連接起來的。為此，在算法中先將輸入的所有邊按權(quán)值進(jìn)行降序排列，然后在建立圖的鄰接表時(shí)，依次考查每一條邊，將該邊的起點(diǎn)和終點(diǎn)分別以頭插法插入到相應(yīng)終點(diǎn)和起點(diǎn)的邊鏈表中。
    (2) 從頂點(diǎn)i開始，申請一個(gè)ＢＴ類的結(jié)點(diǎn)t，其中t->parent＝NULL，t->brother=NULL，t->first=NULL，t->data=i，visited[i]=1，r=t，并且將t結(jié)點(diǎn)加入q隊(duì)列。
    (3)若q隊(duì)列未空，將隊(duì)首元素出隊(duì),即u=q[++front]，并獲取u->data在鄰接表中的邊鏈表的頭指針，即p=g[u->data]->firstarc，設(shè)置一個(gè)標(biāo)志變量k=1（當(dāng)k為１時(shí)，說明剛出隊(duì)的隊(duì)首結(jié)點(diǎn)u的邊鏈表中還沒有一個(gè)未被訪問的結(jié)點(diǎn)加入到目標(biāo)路徑中）。
    一個(gè)結(jié)點(diǎn)剛出隊(duì)時(shí)，該結(jié)點(diǎn)的邊鏈表中肯定還沒有一個(gè)結(jié)點(diǎn)被加入到目標(biāo)路徑中，因此該結(jié)點(diǎn)將作為它的邊鏈表中的結(jié)點(diǎn)的雙親結(jié)點(diǎn)。
    (4) 若p非空（即雙親結(jié)點(diǎn)邊鏈表還未訪問完），則獲取w=p->adindex，并按序執(zhí)行進(jìn)行如下三種情況：
    ①若p指向的結(jié)點(diǎn)未被訪問過，即：visited[w]=0，且k=1，則說明結(jié)點(diǎn)w是雙親結(jié)點(diǎn)的邊鏈表中第一個(gè)未被訪問過的結(jié)點(diǎn)，故w應(yīng)該加入目標(biāo)結(jié)構(gòu)中成為雙親u的first。因此為 w申請一個(gè)ＢＴ類的結(jié)點(diǎn)空間t，此時(shí)，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 隊(duì)列。
    ②若p指向的結(jié)點(diǎn)未被訪問過，且k=0， 則說明w不是雙親結(jié)點(diǎn)的邊鏈表中第一個(gè)未被訪問過的結(jié)點(diǎn)，故w應(yīng)作為前一個(gè)未被訪問結(jié)點(diǎn)t的brother而加入到目標(biāo)結(jié)構(gòu)中。因此申請一個(gè)BT類結(jié)點(diǎn)空間t，t只能作為r的兄弟連接，t的雙親仍為u,即：r->brother=t，t->parent=u，t->first=NULL，t->brother=NULL，t->data=w，r=t。
    ③若p指向的結(jié)點(diǎn)w未被訪問過，則置visited[w]為1且k為0。此時(shí)再做如下判斷：
    若t->data＝＝j(luò)，說明了剛加入目標(biāo)結(jié)構(gòu)中的結(jié)點(diǎn)就是終點(diǎn)，最短路徑已經(jīng)找到。因此從t開始按雙親域?qū)訉酉蛏纤阉髂繕?biāo)結(jié)構(gòu)并一一輸出每個(gè)結(jié)點(diǎn)的data域，直到結(jié)點(diǎn)為空為止，輸出的就是要找的路徑，結(jié)束本算法。
    若t->data!=j說明剛加入目標(biāo)結(jié)構(gòu)的結(jié)點(diǎn)還不是終點(diǎn)，則繼續(xù)考慮邊鏈表的下一個(gè)結(jié)點(diǎn)，即p=p->nextarc，轉(zhuǎn)④繼續(xù)。
    ④若p指向的結(jié)點(diǎn)w已被訪問過,則p=p->nextarc，轉(zhuǎn)4）繼續(xù)。
    (5) 若p為空，說明雙親u的邊鏈表已全部經(jīng)遍歷，應(yīng)該從隊(duì)列出取出一個(gè)新的結(jié)點(diǎn)繼續(xù)考查。故轉(zhuǎn)③繼續(xù)。    (6) 若q已空，則說明從i到j(luò)無路徑，算法結(jié)束。
2 實(shí)例
    以下以一個(gè)交通圖為例,求任意兩點(diǎn)之間的邊數(shù)最少且權(quán)之和也最小的最短路徑。如圖4所示。
    在該圖中各頂點(diǎn)分別代表不同的城市名，兩點(diǎn)之間有邊相連代表兩個(gè)頂點(diǎn)鄰接，邊上的權(quán)值代表兩點(diǎn)之間乘車的費(fèi)用。
    問題:尋找從1~５的邊數(shù)最少且權(quán)之和最小的路徑。
    圖4所建的鄰接表如圖5所示。

    按照上述算法所得的目標(biāo)結(jié)構(gòu)圖如圖6所示。

    從終點(diǎn)5開始按praent域?qū)訉酉蛏纤阉髦钡浇Y(jié)點(diǎn)為
空為止，得一結(jié)點(diǎn)序列5，4，2，1，因此，1->2->4->5就是該問題要找的從結(jié)點(diǎn)1到結(jié)點(diǎn)5的最短路徑，其權(quán)之和6也是相同邊數(shù)的路徑中權(quán)之和最小的一個(gè)。
    本文采用了圖的鄰接表結(jié)構(gòu)以及層次遍歷思想，給出了一種確定任意兩點(diǎn)之間中轉(zhuǎn)邊數(shù)最少且權(quán)值最小的最短路徑的算法，并給出了一個(gè)實(shí)例。這種算法并不是最理想的，但至少是一種有效的實(shí)現(xiàn)方法，還有待于進(jìn)一步優(yōu)化和改進(jìn)。
參考文獻(xiàn)
[１] 張群哲．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）[M].西安:西安電子科技出版社，2008：131-140.
[２] 安訓(xùn)國,劉俞．?dāng)?shù)據(jù)結(jié)構(gòu)（第三版）.[M]大連:大連理工大學(xué)出版社，2003：136-160.