欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python3實現(xiàn)無權最短路徑的方法

 更新時間:2021年05月12日 10:19:57   作者:anlian523  
這篇文章主要介紹了python3實現(xiàn)無權最短路徑的方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

問題描述

現(xiàn)有一個有向無權圖。如下圖所示:

這里寫圖片描述 

問題:使用某個頂點s作為輸入?yún)?shù),找出從s到所有其他頂點的最短路徑。
說明:因為是無權圖,因此我們可以為每臺邊賦值為1。這里選擇v3為s作為起點。

問題分析

此時立刻可以說,從s到v3的最短路徑是長為0的路徑,標記此信息,得到下圖。

這里寫圖片描述 

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

這里寫圖片描述 

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

這里寫圖片描述 

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

這里寫圖片描述 

這種搜索圖的方法稱為廣度優(yōu)先搜索(breadth-first search)。按層處理頂點,距離起點近的頂點先處理,距離起點遠的后處理。

偽代碼(處理節(jié)點)

void unweighted(Vertex s){
    Queue<Vertex> q = new Queue<Vertex>();
    //把每個頂點的距離設為無窮大
    for each Vertex v
        v.dist = INFINITY
    //將起點的距離設為0
    s.dist = 0;
    //起點入隊,作為算法的開始
    q.enqueue(s);
    //只要隊列不為空,便繼續(xù)循環(huán)
    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的上一個經(jīng)過的頂點為v
                //完成操作后,便入隊,以用來接著分析與w鄰接的頂點們
                q.enqueue( w );
            }
    }
}

實現(xiàn)過程

這里寫圖片描述 

這里寫圖片描述 

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

初始化時,將起點的距離設置為0,且所有的頂點都不是know的。

這里寫圖片描述 

結合偽代碼進行分析:
【1】當?shù)谝淮窝h(huán)中,出隊的是v3(每次循環(huán)只出隊一個頂點)
【2】而第一次循環(huán)結束時,就是上表中“v3出隊后”的數(shù)據(jù)情況,如下
【3】此時,對v3的鄰接的頂點們都作了處理,所以v3就從F變成了T(即已知)
【4】與v3鄰接的頂點v1,v6都作了處理,dv都變成了1,pv都為v3
【5】而因為與v1,v6的鄰接頂點都還沒有開始處理呢,所以v1,v6的F還不能變成T

得到無權最短路徑

通過觀察圖,可以發(fā)現(xiàn)有兩條路徑長為3的最短路徑。
【1】v3 => v1 => v2 => v5
【2】v3 => v1 => v4 => v7
我們可以通過數(shù)據(jù)變化表的最終情況來找到這兩條路徑。

這里寫圖片描述 

注意,第一行代表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的頂點,沒有,結束。
其實,以上步驟,是給出了,在對頂點進行數(shù)據(jù)處理后,找出無權最短路徑的算法的思想。
其實可以,維護一些頂點間指針,用來指向下一個頂點,這樣就可以用遞歸的思路來做,從起點開始,每遞歸到下一層距離dv便加1,用一個中間變量存儲經(jīng)過的頂點,每調用一次遞歸,便打印這個中間變量,這樣,便能得到所有的無權最短路徑。
這里得到無權最短路徑的偽代碼也不給出了,以上分析供大家理解參考。

代碼實現(xiàn)

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

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

#創(chuàng)建頂點對象
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)建一個長度為8的數(shù)組,來存儲頂點,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)

運行結果:

這里寫圖片描述 

與數(shù)據(jù)變化表的最終情況一致。
這里你可能會問,Vertex類的init函數(shù)中,明明有know成員,為什么在程序沒有使用know成員(在處理節(jié)點后,就把該節(jié)點的know置為Ture),因為if(vlist[w].dist == float('inf'))的判斷就相當于判斷節(jié)點的know是否為Ture,因為一個已知的節(jié)點,它的距離就肯定不是無窮大了。
然后再使用遞歸,打印出所有可能的最短路徑,把以下代碼和以上代碼合在一起就可以了。

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實現(xiàn)無權最短路徑的方法的文章就介紹到這了,更多相關python3 無權最短路徑內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • Python使用Selenium時遇到網(wǎng)頁<body>劃不動的問題解決方法

    Python使用Selenium時遇到網(wǎng)頁<body>劃不動的問題解決方法

    如果在使用 Selenium 時遇到網(wǎng)頁的 <body> 劃不動的問題,這通常是因為頁面的滾動機制(例如,可能使用了一個具有固定高度的容器或自定義的滾動條)導致無法通過簡單的 JavaScript 實現(xiàn)滾動,可以通過以下方法來解決該問題
    2024-10-10
  • Python+Turtle制作獨特的表白圖

    Python+Turtle制作獨特的表白圖

    這篇文章主要利用Python和Turtle庫繪制獨特的表白圖,文中的示例代碼講解詳細,對我們學習Python有一定的幫助,感興趣的可以了解一下
    2022-04-04
  • python生成1行四列全2矩陣的方法

    python生成1行四列全2矩陣的方法

    今天小編就為大家分享一篇python生成1行四列全2矩陣的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-08-08
  • Python實現(xiàn)多線程HTTP下載器示例

    Python實現(xiàn)多線程HTTP下載器示例

    本篇文章主要介紹了Python實現(xiàn)多線程HTTP下載器示例,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-02-02
  • Python GUI編程學習筆記之tkinter事件綁定操作詳解

    Python GUI編程學習筆記之tkinter事件綁定操作詳解

    這篇文章主要介紹了Python GUI編程學習筆記之tkinter事件綁定操作,結合實例形式分析了Python GUI編程tkinter事件綁定常見操作技巧與使用注意事項,需要的朋友可以參考下
    2020-03-03
  • 簡單學習Python多進程Multiprocessing

    簡單學習Python多進程Multiprocessing

    這篇文章主要和大家一起簡單的學習Python多進程Multiprocessing ,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-08-08
  • python驗證多組數(shù)據(jù)之間有無顯著差異

    python驗證多組數(shù)據(jù)之間有無顯著差異

    這篇文章主要介紹了python驗證多組數(shù)據(jù)之間有無顯著差異,利用方差分析和卡方分布驗證多組數(shù)據(jù)之間的某些屬性有無顯著性差異,對于連續(xù)性屬性可以用方差分析,對于離散型屬性可以用卡方檢驗。下面文章詳細內容需要的小伙伴可以參考一下
    2022-01-01
  • 完美解決python遍歷刪除字典里值為空的元素報錯問題

    完美解決python遍歷刪除字典里值為空的元素報錯問題

    下面小編就為大家?guī)硪黄昝澜鉀Qpython遍歷刪除字典里值為空的元素報錯問題。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-09-09
  • python二元表達式用法

    python二元表達式用法

    今天小編就為大家分享一篇python二元表達式用法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-12-12
  • 在Python中使用xlrd和xlwt讀寫Excel文件代碼實例

    在Python中使用xlrd和xlwt讀寫Excel文件代碼實例

    這篇文章主要介紹了在Python中使用xlrd和xlwt讀寫Excel文件代碼實例,python操作excel主要用到xlrd和xlwt兩個庫,即xlrd是讀excel,xlwt是寫excel庫,文中提供了部分實例代碼,需要的朋友可以參考下
    2023-08-08

最新評論