第python3實(shí)現(xiàn)無權(quán)最短路徑的方法問題：使用某個(gè)頂點(diǎn)s作為輸入?yún)?shù)，找出從s到所有其他頂點(diǎn)的最短路徑。

說明：因?yàn)槭菬o權(quán)圖，因此我們可以為每臺(tái)邊賦值為1。這里選擇v3為s作為起點(diǎn)。

此時(shí)立刻可以說，從s到v3的最短路徑是長(zhǎng)為0的路徑，標(biāo)記此信息，得到下圖。

現(xiàn)在開始尋找從s出發(fā)距離為1的頂點(diǎn)。這些頂點(diǎn)肯定是與s鄰接的頂點(diǎn)，很明顯，v1，v6從s出發(fā)只需要一條邊就到了。所以，從s出發(fā)距離為1的頂點(diǎn)，為v1,v6。

現(xiàn)在開始尋找從s出發(fā)距離為2的頂點(diǎn)。這些頂點(diǎn)肯定是與v1,v6（距離為1的頂點(diǎn)）鄰接的頂點(diǎn)。發(fā)現(xiàn)與v1鄰接的頂點(diǎn)為v2,v4，與v6鄰接的頂點(diǎn)沒有（不能往回走，沒有出邊）。所以，從s出發(fā)距離為2的頂點(diǎn)，為v2,v4。

最后，考察與v2,v4鄰接的頂點(diǎn)，即v5,v7。所以，從s出發(fā)距離為3的頂點(diǎn)，為v5,v7。

這種搜索圖的方法稱為廣度優(yōu)先搜索（breadth-firstsearch）。按層處理頂點(diǎn)，距離起點(diǎn)近的頂點(diǎn)先處理，距離起點(diǎn)遠(yuǎn)的后處理。

偽代碼（處理節(jié)點(diǎn)）

voidunweighted(Vertexs){

QueueVertexq=newQueueVertex

//把每個(gè)頂點(diǎn)的距離設(shè)為無窮大

foreachVertexv

v.dist=INFINITY

//將起點(diǎn)的距離設(shè)為0

s.dist=0;

//起點(diǎn)入隊(duì)，作為算法的開始

q.enqueue(s);

//只要隊(duì)列不為空，便繼續(xù)循環(huán)

while(!q.isEmpty()){

//獲得出隊(duì)頂點(diǎn)

Vertexv=q.dequeue();

//對(duì)與v鄰接的每個(gè)頂點(diǎn)進(jìn)行處理

foreachVertexwadjacenttov

if(w.dist==INFINITY){

w.dist=v.dist+1;

w.path=v;//代表w的上一個(gè)經(jīng)過的頂點(diǎn)為v

//完成操作后，便入隊(duì)，以用來接著分析與w鄰接的頂點(diǎn)們

q.enqueue(w);

}

從s開始到頂點(diǎn)的距離放到dv列里，pv列用來代表，當(dāng)前行代表的頂點(diǎn)的上一個(gè)經(jīng)過的頂點(diǎn)。known列代表此頂點(diǎn)已經(jīng)被處理過了。

初始化時(shí)，將起點(diǎn)的距離設(shè)置為0，且所有的頂點(diǎn)都不是know的。

結(jié)合偽代碼進(jìn)行分析：

【1】當(dāng)?shù)谝淮窝h(huán)中，出隊(duì)的是v3（每次循環(huán)只出隊(duì)一個(gè)頂點(diǎn)）

【2】而第一次循環(huán)結(jié)束時(shí)，就是上表中“v3出隊(duì)后”的數(shù)據(jù)情況，如下

【3】此時(shí)，對(duì)v3的鄰接的頂點(diǎn)們都作了處理，所以v3就從F變成了T（即已知）

【4】與v3鄰接的頂點(diǎn)v1,v6都作了處理，dv都變成了1，pv都為v3

【5】而因?yàn)榕cv1,v6的鄰接頂點(diǎn)都還沒有開始處理呢，所以v1,v6的F還不能變成T

得到無權(quán)最短路徑

通過觀察圖，可以發(fā)現(xiàn)有兩條路徑長(zhǎng)為3的最短路徑。

【1】v3=v1=v2=v5

【2】v3=v1=v4=v7

我們可以通過數(shù)據(jù)變化表的最終情況來找到這兩條路徑。

注意，第一行代表v1，以此類推。

以找到v3=v1=v2=v5路徑為例，過程如下：

【1】找到距離為0的頂點(diǎn)，0在且只在第三行，所以第一個(gè)頂點(diǎn)為v3

【2】找到距離為1且pv為v3的頂點(diǎn)，有第一行和第六行，這里必須選一個(gè)，這里選第一行，所以第二個(gè)頂點(diǎn)為v1

【3】找到距離為2且pv為v1的頂點(diǎn)，有第二行和第四行，這里選第二行，所以第三個(gè)頂點(diǎn)為v2

【4】找到距離為3且pv為v2的頂點(diǎn)，只有第五行，所以第四個(gè)頂點(diǎn)為v5

【5】找到距離為4且pv為v5的頂點(diǎn)，沒有，結(jié)束。

其實(shí)，以上步驟，是給出了，在對(duì)頂點(diǎn)進(jìn)行數(shù)據(jù)處理后，找出無權(quán)最短路徑的算法的思想。

其實(shí)可以，維護(hù)一些頂點(diǎn)間指針，用來指向下一個(gè)頂點(diǎn)，這樣就可以用遞歸的思路來做，從起點(diǎn)開始，每遞歸到下一層距離dv便加1，用一個(gè)中間變量存儲(chǔ)經(jīng)過的頂點(diǎn)，每調(diào)用一次遞歸，便打印這個(gè)中間變量，這樣，便能得到所有的無權(quán)最短路徑。

這里得到無權(quán)最短路徑的偽代碼也不給出了，以上分析供大家理解參考。

紙上得來終覺淺，絕知此事要躬行！還是覺得用代碼實(shí)現(xiàn)一遍比較好。

fromqueueimportQueue

classVertex:

#頂點(diǎn)類

def__init__(self,vid,outList):

self.vid=vid#出邊

self.outList=outList#出邊指向的頂點(diǎn)id的列表，也可以理解為鄰接表

self.know=False#默認(rèn)為假

self.dist=float('inf')#s到該點(diǎn)的距離,默認(rèn)為無窮大

self.prev=0#上一個(gè)頂點(diǎn)的id，默認(rèn)為0

#創(chuàng)建頂點(diǎn)對(duì)象

v1=Vertex(1,[2,4])

v2=Vertex(2,[4,5])

v3=Vertex(3,[1,6])

v4=Vertex(4,[3,5,6,7])

v5=Vertex(5,[7])

v6=Vertex(6,[])

v7=Vertex(7,[6])

#創(chuàng)建一個(gè)長(zhǎng)度為8的數(shù)組，來存儲(chǔ)頂點(diǎn)，0索引元素不存

vlist=[False,v1,v2,v3,v4,v5,v6,v7]

defunweighted():

#起點(diǎn)為v3

vlist[3].dist=0

q=Queue()

q.put(vlist[3])

while(notq.empty()):

v=q.get()#返回并刪除隊(duì)列頭部元素

forwinv.outList:

if(vlist[w].dist==float('inf')):

vlist[w].dist=v.dist+1

vlist[w].prev=v.vid

q.put(vlist[w])

unweighted()

print('v1.prev:',v1.prev,'v1.dist',v1.dist)

print('v2.prev:',v2.prev,'v2.dist',v2.dist)

print('v3.prev:',v3.prev,'v3.dist',v3.dist)

print('v4.prev:',v4.prev,'v4.dist',v4.dist)

print('v5.prev:',v5.prev,'v5.dist',v5.dist)

print('v6.prev:',v6.prev,'v6.dist',v6.dist)

print('v7.prev:',v7.prev,'v7.dist',v7.dist)

運(yùn)行結(jié)果：

與數(shù)據(jù)變化表的最終情況一致。

這里你可能會(huì)問，Vertex類的init函數(shù)中，明明有know成員，為什么在程序沒有使用know成員（在處理節(jié)點(diǎn)后，就把該節(jié)點(diǎn)的know置為Ture），因?yàn)閕f(vlist[w].dist==float('inf'))的判斷就相當(dāng)于判斷節(jié)點(diǎn)的know是否為Ture，因?yàn)橐粋€(gè)已知的節(jié)點(diǎn)，它的距離就肯定不是無窮大了。

然后再使用遞歸，打印出所有可能的最短路徑，把以下代碼和以上代碼合在一起就可以了。

traj_list=[3]#v3是起點(diǎn)直接加上

defprint_traj(dist):

last=traj_list[-1]

print(traj_list,'該路徑的長(zhǎng)度為：',vlist[last].dist)

temp_list=[]#存儲(chǔ)下一步的選項(xiàng)

foriinrange(1,len(vlist)):

v=vlist[i]

if((v.dist==dist)and