周勤,周炳生

（1.金陵科技學院圖書館,江蘇南京211169；2.南京大學信息管理學院,江蘇南京210093）

求兩點間最短路徑是網(wǎng)絡中最基本的問題之一,已有一些方法,如：D（Dijkstra）算法[1-2]、A*算法、SPFA算法、Floyd-Warshali算法、Johnson算法等[2].在實際中,有些求最優(yōu)問題,可轉化為網(wǎng)絡中最短路徑問題[3-4].在這些算法中,D算法為其代表,但這些算法只能用以求最短路徑.文獻[5]中,首次引入延長矩陣的概念,用來表示網(wǎng)絡中點與點和邊的關系,從而使求最短路徑的延長可用點與延長矩陣的運算來表示.實際中有些求最優(yōu)問題,除了要獲得最優(yōu)的第一方案外,還希望獲得次優(yōu)的第二方案、…、第λ方案.文獻[6]中,首次引入λ階短路徑的概念并介紹相應的Z算法,Z算法可根據(jù)給予的λ值,獲得最優(yōu)的第一方案、次優(yōu)的第二方案、…、第λ方案.該算法可同時處理多始點與終點,處理方法是由一點延長到相鄰的所有點后才作下一步處理（參閱該文獻中的例）,為橫向延長,數(shù)據(jù)較多,處理不方便.文獻[7]中,分析了延長產(chǎn)生的相關兩條路徑的階的相互關系,獲得λ階短路徑的構造原則,并得到λ階短路徑的D算法.算法的處理過程,用D算法生成表來表示（參閱該文獻中的例）,處理也不太方便.本文采用文獻[5]的延長矩陣的概念,設計了一種λ階短路徑的最小邊序號算法.

1 λ階短路徑最小邊序號法

連通網(wǎng)絡G（n,m）中點的集合記為V={x1…xn},邊的集合記為E={ek}={（xixj）},其中點的個數(shù)為n=│V│,邊的個數(shù)為m=│E│,邊的權wk（xixj）＞0,邊（xixj）中xi為xj和邊（xixj）的前導點,xj為xi和邊（xixj）的后繼點,xi的所有相鄰邊的集合記為Γ（xi）.從xi不斷沿相鄰邊延長到xj的點序列xi…xk…xj中,除了xj=xi外,其他點都不相同的序列為回路,而沒有相同點則為xi到xj的路徑,其他情況則為通路.路徑中邊的個數(shù)為路徑的長度,路徑的長度≤n-1.xi到xj的路徑中所有邊的權wk（xixj）的和為該路徑的權W.

定義1 xi的相鄰邊集合Γ（xi）中,邊按權值從小到大排序的集合稱為有序邊集合Γyx（xi）,即Γyx（xi）={ttxj/wk（xixj）│tt=1到│Γ（xi）│,（xixj）∈Γ（xi）},其中tt為邊（xixj）的權wk（xixj）在Γ（xi）中排序的序號,權值相同的邊序號相連.

定義2 Eyx為Γ（n,m）的有序邊延長矩陣

其中Eyx中的項：當邊（xixj）屬于Γyx（xi）時有ttxj/wk（xixj）,當邊（xixj）不屬于Γyx（xi）時ttxj/wk（xixj）為空白.Eyx中項顯示tt的稱為顯式有序邊延長矩陣.序號tt可省去,而由矩陣的列數(shù)來表示,稱Eyx中項沒有顯示tt的為隱式有序邊延長矩陣.

連通網(wǎng)絡G（n,m）中任兩點都存在路徑,從xi開始可以不斷和有序邊延長矩陣Eyx進行延長運算,延長到xj的序列為xi…ttxk/wk（xixk）…xj或xi…xk/wk（xixk）…xj.

定義3稱路徑序列xi…ttxk/wk（xixk）…xj為xi到xj的顯式有序邊點序列.xi…ttxk/wk（xixk）…xj為xi到xj的隱式有序邊點序列.

序列xi…ttxk/wk（xixk）…xj中,項ttxk/wk（xixk）之間可用空格分開,以便識別,但通常用點序列L=xi…xk…xj/W來表示即可,其中W為點序列L的權.

定義4當點序列L=xi…xk…xj/W為路徑,而xj為所求終點時,則L為結果路徑.

xi到xj路徑中相鄰兩點是由邊的前導點和后繼點構成的.網(wǎng)絡中任意1條路徑最大長度≤n-1,從xi最多可延長n-1次.當點序列L為通路、回路、結果路徑時,再延長也不能構成新的路徑,便可結束該點序列L的延長.根據(jù)文獻[5],點序列L=xi…xk…xk/W與有序邊延長矩陣Eyx進行延長運算L○+Eyx,是從Eyx的xk行的列中取出所有分別相關的點添加到L末,而獲得新的L矩陣.而這里使用的最小邊序號延長法,每次只選擇有序邊延長矩陣中一條可用的序號最小的邊進行延長.這樣獲得的新L矩陣中只有1條點序列L,該點序列L其實是在原L的末點添加Eyx中1個相關的點.所以,這里L與有序邊延長矩陣Eyx進行的延長運算L○+Eyx,可直接用“在L的末點添加有序邊延長矩陣Eyx中相關的1個點”來表示延長運算過程.

這樣,求始點xi的點序列L的最小邊序號延長法是：從L=xi開始（即xi為始點）,每次選L末點為行,而相應Eyx中列為序號1的邊延長.當點序列L為通路、回路、結果路徑（結果路徑需另外保存）時,則后退到剛延長邊的前導點,即刪除點序列L的末點,如剛后退獲得的新L仍不能延長,則繼續(xù)后退.后退后L首先選比該末點已選邊序號大1的邊延長,以后仍選序號為1的邊延長.如此反復這些操作,直到點序列L中只有唯一點xi,有序邊延長矩陣Eyx中xi行又沒有可用以延長的邊,便結束操作.

上述最小邊序號延長法,保證xi到xj的所有結果路徑都被選過1次,從而獲得所有結果路徑.因為,如結果路徑L0未被選到過,被選過的結果路徑中一定有一條與L0路徑相比,這兩條路徑中,從xi開始一定具有一段相同點的點序列（因至少xi相同）,而該段點序列末點的后一個點一定不同（否則兩條路徑一樣）,這表明這里的邊有不同的邊序號,如該處L0比該路徑的邊序號大,則L0在該路徑以后應被選；如L0比該路徑的邊序號小,則L0應在該路徑以前被選.否則與選法矛盾,故L0亦在結果路徑中.

定義5 xi到xj的所有路徑按路徑權的大小排序,序號為λ的路徑稱為λ階路徑.規(guī)定λ=1為最短路徑,λ=2為次短路徑,其他類推.

在求xi到xj的λ階短路徑中,只要求1到λ階的短路徑,不必一定求出所有路徑.

定義6令P為存1到λ階的短路徑的集合.B為存1到λ階的短路徑權的集合,即B={w（k）│k=1…λ}.令 B 中最大權 Mw=max{w（k）│k=1…λ},B 中最小權 mw=min{w（k）│k=1…λ}.

在求xi到xj的λ階短路徑中,當│B│=λ時,如正在延長的路徑的權值已大于Mw值再延長,獲得的新路徑的權值將更大于Mw值,故這樣的路徑不需要再延長.

定義7當│B│=λ時,點序列L為路徑且L的權≥Mw,則L為無效路徑.

定義8 Eyx中可以被選用的邊為顯性邊,不可以被選用的邊為隱性邊.

定義9刪除點序列末點的操作為后退.

定義10點序列延長后增加的點為新延長點.后退操作后點序列的末點為后退延長點.

因此,點序列L的延長操作,即為在L末添點.而L的后退操作,即為在點序列L末刪除點.

根據(jù)前面的最小邊序號延長法,可獲得下面的λ階短路徑的最小邊序號法.

（1）初值：

令 L=xi,始點 xi為新延長點,P=｛｝,B=｛｝,Mw=0,mw=0,Eyx中邊為顯性邊.給 λ 值（λ≥1）.

（2）每次獲得的點序列L的處理：

①若為通路、回路,則點序列L后退.

②若為路徑,求路徑的權值W：

a.如為結果路徑,當│B│小于λ時,則將路徑權值W存入B,結果路徑存入P,計算Mw和mw,點序列后退.

b.如為結果路徑,當│B│=λ時,而路徑權值W大于Mw,則路徑為無效路徑,點序列L后退.

c.如為結果路徑,當│B│=λ時,而路徑權值W∈B,則將結果路徑存入P,點序列L后退.

d.如為結果路徑,當│B│=λ時,而路徑權值W小于Mw且W不屬于B,則將結果路徑存入P,權值W存入B,刪除P中最大權值的結果路徑,刪除B中最大值和計算新Mw和mw,點序列L后退.

e.如不為結果路徑,當│B│小于λ時,則點序列L的最后點為新延長點,點序列L繼續(xù)延長.

f.如不為結果路徑,當│B│=λ時,而權值W≥Mw,則路徑為無效路徑,點序列L后退.

g.如不為結果路徑,當│B│=λ時,權值W小于Mw,則點序列L的最后點為新延長點,點序列L繼續(xù)延長.

（3）后退操作后的處理：

①如后退后xi為點序列L中唯一的點,且xi的所有相鄰邊均為隱性邊,則結束處理.

②如后退后序列L的最后點不為始點xi,若其所有相鄰邊均為隱性邊,則該點的相鄰邊變?yōu)轱@性邊,繼續(xù)后退.

③如后退后序列L的末點不為始點xi,若其所有相鄰邊有顯性邊,則序列L的最后點為后退延長點,繼續(xù)延長.

（4）延長的方法：

①新延長點：每次選Eyx中該點行的相應第1列的邊（即序號為1邊）延長（因均為顯性邊）,延長后該邊為隱性邊.

②后退延長點：每次選Eyx中該點行的相應列的序號最小的顯性邊（即比隱性邊序號再大于1的邊）延長.

這樣,點序列L延長選邊的方法：除后退后的第一次選序號增加1的邊外,其他都選序號為1的邊.

2 例證及討論

2.1 例證

例：求圖中x1到x5,λ=2的短路徑.

解：根據(jù)上圖,可獲得隱式有序邊延長矩陣

有初值：L=x1,始點 x1為新延長點,P=｛｝,B=｛｝,Mw=0,mw=0,λ=2（求最短和次短路徑）.

下面L○+Eyx延長運算及獲得結果L的處理,用處理過程中的部分點序列L和相應說明來表明.在點序列L處理過程中,后退操作后獲得的L的末點為后退延長點,同時還表示從始點到該點為原L中需保留的那些點.被刪除的點用字符加框標明,而后退延長點用下劃線標明.

各處理過程說明如下：

（1）L為先取有序邊延長矩陣x1行的第1列的邊（x1x2）（邊序號為1）延長,以后取有序邊延長矩陣x2行的第1列的邊（x2x1）（邊序號為1）延長而得.L為回路,刪除末點x1,x2為后退延長點.

（2）L為x2選有序邊延長矩陣x2行第2列邊（x2x3）（邊序號為2的顯性邊）延長到x3,x3為新延長點.

（3）延長到x2后L為通路,刪除末點x2,x3為后退延長點.

（4）經(jīng)不斷的延長和后退獲得的L為x4經(jīng)有序邊延長矩陣x4行的第3列邊（x4x6）（邊序號為3）延長而得,x6為新延長點.

（5）L為通路,刪除末點x4,x6為后退延長點.

（6）L 為第 1 條結果路徑,存入后 P=｛x1x2x3x4x6x5/7｝,B=｛7｝,Mw=7,mw=0.刪除末點 x5.

（7）L 為第 2 條結果路徑,存入后 P=｛x1x2x3x4x6x5/7,x1x2x3x4x6x7x5/16｝,B=｛7,16｝,Mw=16,mw=7.刪除末點 x5.

（8）L取邊序號為2的邊（x7x6）延長到x6后為通路,刪除末點x6后,后退延長點x7因沒有顯性邊可用以延長,刪除末點x7后,x6又為后退延長點,同樣因沒有顯性邊,仍要刪除末點x6,使x4為后退延長點.

（9）L為第3條結果路徑,存入P且刪除P中權為16的路徑,有P=｛x1x2x3x4x6x5/7,x1x2x4x6x5/6｝,B=｛7,6｝,Mw=7,mw=6.刪除末點x5,x6為后退延長點.

（10）因L的權為13,已大于7（Mw=7）,L為無效路徑,刪除末點x7,x6為后退延長點,因點x6沒有顯性邊可用以延長,又刪除末點x6,x4為后退延長點,x4選邊序號為4的邊（x4x1）延長到x1后為回路,刪除末點x1,又因點x4沒有顯性邊可用以延長,又刪除末點x4,使x2為后退延長點.

（11）因L中只有點x1為后退延長點,又沒有顯性邊可用以延長,所以結束處理.

最后得：P=｛x1x2x4x6x5/6,x1x2x3x4x6x5/7｝,B=｛6,7｝,Mw=7,mw=6.即：λ=1 的最短路徑為 x1x2x4x6x5/6,λ=2 的次短路徑為x1x2x3x4x6x5/7.

2.2 討論

在處理過程中,處理的復雜性顯然與網(wǎng)絡的結構、相同權值的邊的先后次序、始點與終點選擇等有關.該算法特點為：①每次從可能的最小序號的邊（即權小的邊）開始延長,希望首先獲得的用于參考的最大和最小權值較小.②采用無效路徑和權值大的邊在較后用于延長,使權值大的路徑在延長中,可能因是無效路徑而終止處理,從而提高效率.③每次延長和后退操作是在點序列末增加或刪除一個點,點序列中其他點不動,操作簡單,適用于手工和計算機處理.④可求得所有符合條件的路徑.⑤如將需保存結果路徑點序列的判別條件改為：回路或哈密頓回路的判別條件[8]、推銷員或中國郵遞員的判別條件[9],則算法將成為相應的λ階短回路的最小邊序號法.故算法具有可移植性和選擇擴展功能的能力.

3 小結

本文設計的λ階短路徑的最小邊序號法為縱向延長,即由一點延長到相鄰的一個點后就作下一步處理,獲得的數(shù)據(jù)單一、處理方便、操作簡單.

[1]祝頌和,陸詩娣,陳建明,等.離散數(shù)學[M].西安：西安交通大學出版社,1991：224-228.

[2]吳華麗,吳進華,王玲玲,等.幾種最短路徑算法的比較[J].計算機科學,2010,37（7A）：196-197,233.

[3]施寅躍.城市道路網(wǎng)中蟻群最短路徑算法的研究[D].南京：南京理工大學,2010.

[4]林月平,李軍.最短路徑算法在工程裝備應急維修決策中的應用[J].科技信息,2011（13）：181.

[5]周炳生.網(wǎng)絡中多始點與終點路徑的延長算法[J].上海技術師范學院學報：自然科學版,1989（1）：32-38.

[6]周勤,周炳生.網(wǎng)絡中短路徑的Z算法[J].金陵職業(yè)大學學報,2002（1）：25-29.

[7]周勤,周炳生.網(wǎng)絡中λ階短路徑的構造原則及算法[J].廣西科學院學報,2008,24（3）：243-247,253.

[8]周炳生,周勤.λ階短哈密頓回路的最小權法[J].廣西科學院學報,2005,21（2）：67-70,75.

[9]周勤,周炳生.網(wǎng)絡中選擇路徑的匹配法[J].科學研究月刊,2008（40）：93-97.