問題描述
現有一個有向無權圖。如下圖所示：
問題：使用某個頂點s作為輸入參數，找出從s到所有其他頂點的最短路徑。
說明：因為是無權圖，因此我們可以為每臺邊賦值為1。這里選擇v3為s作為起點。
問題分析
此時立刻可以說，從s到v3的最短路徑是長為0的路徑，標記此信息，得到下圖。
現在開始尋找從s出發距離為1的頂點。這些頂點肯定是與s鄰接的頂點，很明顯，v1，v6從s出發只需要一條邊就到了。所以，從s出發距離為1的頂點，為v1,v6。
現在開始尋找從s出發距離為2的頂點。這些頂點肯定是與v1,v6（距離為1的頂點）鄰接的頂點。發現與v1鄰接的頂點為v2,v4，與v6鄰接的頂點沒有（不能往回走，沒有出邊）。所以，從s出發距離為2的頂點，為v2,v4。
最后，考察與v2,v4鄰接的頂點，即v5,v7。所以，從s出發距離為3的頂點，為v5,v7。
這種搜索圖的方法稱為廣度優先搜索（breadth-first search）。按層處理頂點，距離起點近的頂點先處理，距離起點遠的后處理。
偽代碼（處理節點）
void unweighted(Vertex s){
QueueVertex> q = new QueueVertex>();
//把每個頂點的距離設為無窮大
for each Vertex v
v.dist = INFINITY
//將起點的距離設為0
s.dist = 0;
//起點入隊，作為算法的開始
q.enqueue(s);
//只要隊列不為空，便繼續循環
while( !q.isEmpty() ){
//獲得出隊頂點
Vertex v = q.dequeue();
//對與v鄰接的每個頂點進行處理
for each Vertex w adjacent to v
if(w.dist == INFINITY){
w.dist = v.dist + 1;
w.path = v;//代表w的上一個經過的頂點為v
//完成操作后，便入隊，以用來接著分析與w鄰接的頂點們
q.enqueue( w );
}
}
}
實現過程
從s開始到頂點的距離放到dv列里，pv列用來代表，當前行代表的頂點的上一個經過的頂點。known列代表此頂點已經被處理過了。
初始化時，將起點的距離設置為0，且所有的頂點都不是know的。
結合偽代碼進行分析：
【1】當第一次循環中，出隊的是v3（每次循環只出隊一個頂點）
【2】而第一次循環結束時，就是上表中“v3出隊后”的數據情況，如下
【3】此時，對v3的鄰接的頂點們都作了處理，所以v3就從F變成了T（即已知）
【4】與v3鄰接的頂點v1,v6都作了處理，dv都變成了1，pv都為v3
【5】而因為與v1,v6的鄰接頂點都還沒有開始處理呢，所以v1,v6的F還不能變成T
得到無權最短路徑
通過觀察圖，可以發現有兩條路徑長為3的最短路徑。
【1】v3 => v1 => v2 => v5
【2】v3 => v1 => v4 => v7
我們可以通過數據變化表的最終情況來找到這兩條路徑。
注意，第一行代表v1，以此類推。
以找到v3 => v1 => v2 => v5路徑為例，過程如下：
【1】找到距離為0的頂點，0在且只在第三行，所以第一個頂點為v3
【2】找到距離為1且pv為v3的頂點，有第一行和第六行，這里必須選一個，這里選第一行，所以第二個頂點為v1
【3】找到距離為2且pv為v1的頂點，有第二行和第四行，這里選第二行，所以第三個頂點為v2
【4】找到距離為3且pv為v2的頂點，只有第五行，所以第四個頂點為v5
【5】找到距離為4且pv為v5的頂點，沒有，結束。
其實，以上步驟，是給出了，在對頂點進行數據處理后，找出無權最短路徑的算法的思想。
其實可以，維護一些頂點間指針，用來指向下一個頂點，這樣就可以用遞歸的思路來做，從起點開始，每遞歸到下一層距離dv便加1，用一個中間變量存儲經過的頂點，每調用一次遞歸，便打印這個中間變量，這樣，便能得到所有的無權最短路徑。
這里得到無權最短路徑的偽代碼也不給出了，以上分析供大家理解參考。
代碼實現
紙上得來終覺淺，絕知此事要躬行！還是覺得用代碼實現一遍比較好。
from queue import Queue
class Vertex:
#頂點類
def __init__(self,vid,outList):
self.vid = vid#出邊
self.outList = outList#出邊指向的頂點id的列表，也可以理解為鄰接表
self.know = False#默認為假
self.dist = float('inf')#s到該點的距離,默認為無窮大
self.prev = 0#上一個頂點的id，默認為0
#創建頂點對象
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])
#創建一個長度為8的數組，來存儲頂點，0索引元素不存
vlist = [False,v1,v2,v3,v4,v5,v6,v7]
def unweighted():
#起點為v3
vlist[3].dist = 0
q = Queue()
q.put(vlist[3])
while(not q.empty()):
v = q.get()#返回并刪除隊列頭部元素
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)
運行結果：
與數據變化表的最終情況一致。
這里你可能會問，Vertex類的init函數中，明明有know成員，為什么在程序沒有使用know成員（在處理節點后，就把該節點的know置為Ture），因為if(vlist[w].dist == float('inf'))的判斷就相當于判斷節點的know是否為Ture，因為一個已知的節點，它的距離就肯定不是無窮大了。
然后再使用遞歸，打印出所有可能的最短路徑，把以下代碼和以上代碼合在一起就可以了。
traj_list = [3]#v3是起點直接加上
def print_traj(dist):
last = traj_list[-1]
print(traj_list,'該路徑的長度為：',vlist[last].dist)
temp_list = []#存儲下一步的選項
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#終點
#遞歸每個選項
for i in temp_list:#i為頂點的索引
traj_list.append(i)
print_traj(dist+1)
traj_list.pop()
print_traj(1)
到此這篇關于python3實現無權最短路徑的方法的文章就介紹到這了,更多相關python3 無權最短路徑內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:- Python實現迪杰斯特拉算法并生成最短路徑的示例代碼
- python實現最短路徑的實例方法
- python Dijkstra算法實現最短路徑問題的方法
- python實現Dijkstra算法的最短路徑問題
- python游戲地圖最短路徑求解
- Python實現的多叉樹尋找最短路徑算法示例
- Python基于Floyd算法求解最短路徑距離問題實例詳解
