python3實(shí)現(xiàn)無權(quán)最短路徑的方法
問題描述
現(xiàn)有一個(gè)有向無權(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-first search)。按層處理頂點(diǎn),距離起點(diǎn)近的頂點(diǎn)先處理,距離起點(diǎn)遠(yuǎn)的后處理。
偽代碼(處理節(jié)點(diǎn))
void unweighted(Vertex s){ Queue<Vertex> q = new Queue<Vertex>(); //把每個(gè)頂點(diǎn)的距離設(shè)為無窮大 for each Vertex v 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) Vertex v = q.dequeue(); //對(duì)與v鄰接的每個(gè)頂點(diǎn)進(jìn)行處理 for each Vertex w adjacent to v 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 ); } } }
實(shí)現(xiàn)過程
從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)
紙上得來終覺淺,絕知此事要躬行!還是覺得用代碼實(shí)現(xiàn)一遍比較好。
from queue import Queue class Vertex: #頂點(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] def unweighted(): #起點(diǎn)為v3 vlist[3].dist = 0 q = Queue() q.put(vlist[3]) while(not q.empty()): v = q.get()#返回并刪除隊(duì)列頭部元素 for w in v.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)?code>if(vlist[w].dist == float('inf'))的判斷就相當(dāng)于判斷節(jié)點(diǎn)的know是否為Ture,因?yàn)橐粋€(gè)已知的節(jié)點(diǎn),它的距離就肯定不是無窮大了。
然后再使用遞歸,打印出所有可能的最短路徑,把以下代碼和以上代碼合在一起就可以了。
traj_list = [3]#v3是起點(diǎn)直接加上 def print_traj(dist): last = traj_list[-1] print(traj_list,'該路徑的長(zhǎng)度為:',vlist[last].dist) temp_list = []#存儲(chǔ)下一步的選項(xiàng) for i in range(1,len(vlist)): v = vlist[i] if((v.dist==dist) and (v.prev==last)): temp_list.append(i) if(len(temp_list)==0): return#終點(diǎn) #遞歸每個(gè)選項(xiàng) for i in temp_list:#i為頂點(diǎn)的索引 traj_list.append(i) print_traj(dist+1) traj_list.pop() print_traj(1)
到此這篇關(guān)于python3實(shí)現(xiàn)無權(quán)最短路徑的方法的文章就介紹到這了,更多相關(guān)python3 無權(quán)最短路徑內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- python編寫的最短路徑算法
- Python數(shù)據(jù)結(jié)構(gòu)與算法之圖的最短路徑(Dijkstra算法)完整實(shí)例
- Python使用Dijkstra算法實(shí)現(xiàn)求解圖中最短路徑距離問題詳解
- python Dijkstra算法實(shí)現(xiàn)最短路徑問題的方法
- Python實(shí)現(xiàn)的多叉樹尋找最短路徑算法示例
- Python實(shí)現(xiàn)最短路徑問題的方法
- python實(shí)現(xiàn)最短路徑的實(shí)例方法
- python3實(shí)現(xiàn)Dijkstra算法最短路徑的實(shí)現(xiàn)
- Python?最短路徑的幾種求解方式
相關(guān)文章
Python使用Selenium時(shí)遇到網(wǎng)頁(yè)<body>劃不動(dòng)的問題解決方法
如果在使用 Selenium 時(shí)遇到網(wǎng)頁(yè)的 <body> 劃不動(dòng)的問題,這通常是因?yàn)轫?yè)面的滾動(dòng)機(jī)制(例如,可能使用了一個(gè)具有固定高度的容器或自定義的滾動(dòng)條)導(dǎo)致無法通過簡(jiǎn)單的 JavaScript 實(shí)現(xiàn)滾動(dòng),可以通過以下方法來解決該問題2024-10-10Python實(shí)現(xiàn)多線程HTTP下載器示例
本篇文章主要介紹了Python實(shí)現(xiàn)多線程HTTP下載器示例,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-02-02Python GUI編程學(xué)習(xí)筆記之tkinter事件綁定操作詳解
這篇文章主要介紹了Python GUI編程學(xué)習(xí)筆記之tkinter事件綁定操作,結(jié)合實(shí)例形式分析了Python GUI編程tkinter事件綁定常見操作技巧與使用注意事項(xiàng),需要的朋友可以參考下2020-03-03簡(jiǎn)單學(xué)習(xí)Python多進(jìn)程Multiprocessing
這篇文章主要和大家一起簡(jiǎn)單的學(xué)習(xí)Python多進(jìn)程Multiprocessing ,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-08-08python驗(yàn)證多組數(shù)據(jù)之間有無顯著差異
這篇文章主要介紹了python驗(yàn)證多組數(shù)據(jù)之間有無顯著差異,利用方差分析和卡方分布驗(yàn)證多組數(shù)據(jù)之間的某些屬性有無顯著性差異,對(duì)于連續(xù)性屬性可以用方差分析,對(duì)于離散型屬性可以用卡方檢驗(yàn)。下面文章詳細(xì)內(nèi)容需要的小伙伴可以參考一下2022-01-01完美解決python遍歷刪除字典里值為空的元素報(bào)錯(cuò)問題
下面小編就為大家?guī)硪黄昝澜鉀Qpython遍歷刪除字典里值為空的元素報(bào)錯(cuò)問題。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-09-09在Python中使用xlrd和xlwt讀寫Excel文件代碼實(shí)例
這篇文章主要介紹了在Python中使用xlrd和xlwt讀寫Excel文件代碼實(shí)例,python操作excel主要用到xlrd和xlwt兩個(gè)庫(kù),即xlrd是讀excel,xlwt是寫excel庫(kù),文中提供了部分實(shí)例代碼,需要的朋友可以參考下2023-08-08