App下載

python3實現(xiàn)Dijkstra算法最短路徑的實現(xiàn)

逃避全世界 2021-08-19 11:11:08 瀏覽數(shù) (3327)
反饋

在圖論中求最短路徑的算法主要有三種,其中最具代表性的當屬Dijkstra算法,那么Dijkstra算法算法要如何在python中實現(xiàn)呢?今天小編就帶你來了解一下。

問題描述

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

這里寫圖片描述

問題:根據(jù)每條邊的權值,求出從起點s到其他每個頂點的最短路徑和最短路徑的長度。
說明:不考慮權值為負的情況,否則會出現(xiàn)負值圈問題。
s:起點
v:算法當前分析處理的頂點
w:與v鄰接的頂點
d v d_v dv?:從s到v的距離
d w d_w dw?:從s到w的距離
c v , w c_{v,w} cv,w?:頂點v到頂點w的邊的權值

問題分析

Dijkstra算法按階段進行,同無權最短路徑算法(先對距離為0的頂點處理,再對距離為1的頂點處理,以此類推)一樣,都是先找距離最小的。
在每個階段,Dijkstra算法選擇一個頂點v,它在所有unknown頂點中具有最小的 d v d_v dv?,同時算法聲明從s到v的最短路徑是known的。階段的其余部分為,對w的 d v d_v dv?(距離)和 p v p_v pv?(上一個頂點)更新工作(當然也可能不更新)。
在算法的每個階段,都是這樣處理的:
【0.5】在無權的情況下,若 d w d_w dw?= ∞ infty ∞則置 d w = d v + 1 d_w=d_v+1 dw?=dv?+1(無權最短路徑)
【1】在有權的情況下,若 d w d_w dw?= ∞ infty ∞則置 d w = d v + c v , w d_w=d_v+c_{v,w} dw?=dv?+cv,w?
【2】若 d w d_w dw?!= ∞ infty ∞,開始分析:從頂點v到頂點w的路徑,若能使得w的路徑長比w原來的路徑長短一點,那么就需要對w進行更新,否則不對w更新。即滿足 d v + c v , w &lt; d w d_v+c_{v,w}&lt;d_w dv?+cv,w?<dw?時,就需要把 d w d_w dw?的值更新為 d v + c v , w d_v+c_{v,w} dv?+cv,w?,同時頂點w的 p v p_v pv?值得改成頂點v

實現(xiàn)過程

考慮Dijkstra算法過程中,有一個數(shù)據(jù)變化表。

這里寫圖片描述

這里寫圖片描述

初始狀態(tài)如上。開始頂點s是 v 1 v_1 v1?,所有頂點都是unknown的。 v 1 v_1 v1?的 d v d_v dv?的值為0,因為它是起點。

【1】選擇unknown頂點中, d v d_v dv?值最小的頂點,即頂點 v 1 v_1 v1?。首先將 v 1 v_1 v1?標記為known。對與 v 1 v_1 v1?鄰接的頂點 v 2 v 4 v_2 v_4 v2?v4?進行調(diào)整: v 2 v_2 v2?的距離變?yōu)?d v + c v , w d_v+c_{v,w} dv?+cv,w?即 v 1 v_1 v1?的 d v d_v dv?值+ c 1 , 2 c_{1,2} c1,2?即0+2=2, v 2 v_2 v2?的 p v p_v pv?值變?yōu)?v 1 v_1 v1?;同理,對 v 4 v_4 v4?作相應的處理。

這里寫圖片描述

【2】選擇unknown頂點中, d v d_v dv?值最小的頂點,即頂點 v 4 v_4 v4?(其距離為1,最?。?。將 v 4 v_4 v4?標記為known。對其鄰接的頂點 v 3 v 5 v 6 v 7 v_3 v_5 v_6 v_7 v3?v5?v6?v7?作相應的處理。

這里寫圖片描述

【3】選擇unknown頂點中, d v d_v dv?值最小的頂點,即頂點 v 2 v_2 v2?(其距離為2,最?。?。將 v 2 v_2 v2?標記為known。對其鄰接的頂點 v 4 v 5 v_4v_5 v4?v5?作相應的處理。但 v 4 v_4 v4?是已知的,所以不需要調(diào)整;因為經(jīng)過 v 2 v_2 v2?到 v 5 v_5 v5?的距離為2+10=12,而s到 v 5 v_5 v5?路徑為3是已知的(上表中, v 5 v_5 v5?的 d v d_v dv?為3),12>3,所以也不需要也沒有必要調(diào)整。

這里寫圖片描述

【4】選擇unknown頂點中, d v d_v dv?值最小的頂點,即頂點 v 5 v_5 v5?(距離為3,最小,其實還有 v 3 v_3 v3?也是距離為3,但博主發(fā)現(xiàn)這里,先 v 5 v_5 v5?再 v 3 v_3 v3?和先 v 3 v_3 v3?再 v 5 v_5 v5?的運行結(jié)果都是一樣的)。將 v 5 v_5 v5?標記為known。對其鄰接的頂點 v 7 v_7 v7?作相應的處理。但原路徑長更小,所以不用調(diào)整。

【5】再對 v 3 v_3 v3?處理。對 v 6 v_6 v6?的距離下調(diào)到3+5=8

這里寫圖片描述

【6】再對 v 7 v_7 v7?處理。對 v 6 v_6 v6?的距離下調(diào)到5+1=6

這里寫圖片描述

【7】最后,再對 v 6 v_6 v6?處理。不需調(diào)整。

這里寫圖片描述

上述實現(xiàn)過程對應的算法,可能需要用到優(yōu)先隊列,每次出隊 d v d_v dv?值最小的頂點,因為如果只是遍歷來找到 d v d_v dv?值最小的頂點,可能會花費很多時間。

如何使用數(shù)據(jù)變化表

數(shù)據(jù)變化表的最終情況如下:

這里寫圖片描述

現(xiàn)在我們能找到起點 v 1 v_1 v1?到任意的 v i v_i vi?(除了起點)的最短路徑,及其最短路徑長。
比如,找到 v 1 v_1 v1?到 v 3 v_3 v3?的最短路徑。
【1】 v 3 v_3 v3?的 d v d_v dv?值為3,所以最短路徑長為3
【2】 v 3 v_3 v3?的 p v p_v pv?值為 v 4 v_4 v4?,所以 v 3 v_3 v3?的上一個頂點為 v 4 v_4 v4?
【3】到代表 v 4 v_4 v4?的第四行,發(fā)現(xiàn) v 4 v_4 v4?的 p v p_v pv?值為 v 1 v_1 v1?,所以 v 4 v_4 v4?的上一個頂點為 v 1 v_1 v1?
【4】 v 1 v_1 v1?是起點,結(jié)束。 v 3 v_3 v3?上一個是 v 4 v_4 v4?, v 4 v_4 v4?上一個是 v 1 v_1 v1?,反過來就得到了最短路徑 v 1 = &gt; v 4 = &gt; v 3 v_1=&gt;v_4=&gt;v_3 v1?=>v4?=>v3?
上述分析,其實就是求最短路徑的算法的思想:在對每個頂點對象進行處理后變成數(shù)據(jù)變化表的最終情況后,可以通過對任意頂點 v i v_i vi?的 p v p_v pv?值,回溯得到反轉(zhuǎn)的最短路徑。

代碼實現(xiàn)

紙上得來終覺淺,絕知此事要躬行!使用python3來實現(xiàn)功能。
本文提到,將使用優(yōu)先隊列來實現(xiàn)尋找未知頂點中,具有最小dist的頂點。使用python已有實現(xiàn)好的優(yōu)先隊列。但實驗中報錯如下:

這里寫圖片描述

意思,Vertex實例并不支持小于比較運算符。所以需要實現(xiàn)Vertex類的__lt__方法。下面科普一下:

方法名 比較運算符 含義
__eq__ == equal
__lt__ < less than
__le__ <= less and equal
__gt__ > greater than
__ge__ >= greater and equal

但很遺憾,python庫自帶的優(yōu)先隊列from queue import PriorityQueue,并不滿足本文的需求。當PriorityQueue的元素為對象時,需要該對象的class實現(xiàn)__lt__函數(shù),在往優(yōu)先隊列里添加元素時,內(nèi)部是用的堆排序,堆排序的特點為每個堆(以及每個子堆)的第一個元素總是那個最小的元素。關鍵在于,在建立了這個堆后,堆就已經(jīng)記錄下來了創(chuàng)建堆時各個元素的大小關系了,在創(chuàng)建優(yōu)先隊列后,再改變某個對象的值,這個堆的結(jié)構是肯定不會變的,所以這種堆排序造成了排序是一次性的,如果之后某個對象的屬性發(fā)生變化,堆的結(jié)構也不會隨之而改變。

或者說,我們想要的優(yōu)先隊列肯定不是系統(tǒng)提供的優(yōu)先隊列,因為我們要支持可變對象的成員修改導致堆的改變,解決方案有三種,1.內(nèi)部使用的堆排序的堆,最起碼要支持,刪除任意節(jié)點和增加節(jié)點操作(因為這兩步就可以達到修改的效果了)2.這個內(nèi)部堆,在執(zhí)行出隊操作時,考察哪個節(jié)點有修改操作,再把堆改變到正確的形態(tài),再出隊3.維護一個list,進行排降序,然后每改變一個可變對象的值,就對這個對象進行冒泡或者二分查找找到位置(因為別的都是已經(jīng)排好序的了,只有它不在正確的位置),最后再list.pop(),但第三個方案是我后來想到的,所以下面代碼并不是這樣實現(xiàn)的,讀者可以進行嘗試,肯定比每次遍歷全部快。

應該說,可能用不上隊列了。我們可能只需要一個list或者set來存儲v,在出隊前隨便vi改變其dist,在出隊時再遍歷找到最小的dist的vi,再刪除掉這個vi即可。因為vi的dist一直在變,需求特殊,但是沒必要專門造個輪子(感覺這個輪子也不好造),雖然時間復雜度可能高了點,但代碼簡單了啊。

優(yōu)先隊列中的堆排序

失效代碼如下:三個節(jié)點對象的dist都是無窮大,在三個對象都進入隊列,再把v3的dist改成0,想要的效果是出隊出v3,但出隊出的是v1。原因如上:

from queue import PriorityQueue
class Vertex:
    #頂點類
    def __init__(self,vid,dist):
        self.vid = vid
        self.dist = dist
    
    def __lt__(self,other):
        return self.dist < other.dist   
v1=Vertex(1,float('inf'))
v2=Vertex(2,float('inf'))
v3=Vertex(3,float('inf'))

vlist = [v1,v2,v3]
q = PriorityQueue()

for i in range(0,len(vlist)):
    q.put(vlist[i])
v3.dist = 0

print('vid:',q.get().vid)#結(jié)果為vid: 1

而如果將在入隊前,就把dist改變了,就能正確的出隊。

v3.dist = 0
for i in range(0,len(vlist)):
    q.put(vlist[i])
#結(jié)果為vid: 3 

使用set代替優(yōu)先隊列

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
    def __eq__(self, other):
        if isinstance(other, self.__class__):
            return self.vid == other.vid
        else:
            return False
    def __hash__(self):
        return hash(self.vid)

#創(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])
#存儲邊的權值
edges = dict()
def add_edge(front,back,value):
    edges[(front,back)]=value
add_edge(1,2,2)
add_edge(1,4,1)
add_edge(3,1,4)
add_edge(4,3,2)
add_edge(2,4,3)
add_edge(2,5,10)
add_edge(4,5,2)
add_edge(3,6,5)
add_edge(4,6,8)
add_edge(4,7,4)
add_edge(7,6,1)
add_edge(5,7,6)
#創(chuàng)建一個長度為8的數(shù)組,來存儲頂點,0索引元素不存
vlist = [False,v1,v2,v3,v4,v5,v6,v7]
#使用set代替優(yōu)先隊列,選擇set主要是因為set有方便的remove方法
vset = set([v1,v2,v3,v4,v5,v6,v7])

def get_unknown_min():#此函數(shù)則代替優(yōu)先隊列的出隊操作
    the_min = 0
    the_index = 0
    j = 0
    for i in range(1,len(vlist)):
        if(vlist[i].know is True):
            continue
        else:
            if(j==0):
                the_min = vlist[i].dist
                the_index = i
            else:
                if(vlist[i].dist < the_min):
                    the_min = vlist[i].dist
                    the_index = i                    
            j += 1
    #此時已經(jīng)找到了未知的最小的元素是誰
    vset.remove(vlist[the_index])#相當于執(zhí)行出隊操作
    return vlist[the_index]

def main():
    #將v1設為頂點
    v1.dist = 0

    while(len(vset)!=0):
        v = get_unknown_min()
        print(v.vid,v.dist,v.outList)
        v.know = True
        for w in v.outList:#w為索引
            if(vlist[w].know is True):
                continue
            if(vlist[w].dist == float('inf')):
                vlist[w].dist = v.dist + edges[(v.vid,w)]
                vlist[w].prev = v.vid
            else:
                if((v.dist + edges[(v.vid,w)])<vlist[w].dist):
                    vlist[w].dist = v.dist + edges[(v.vid,w)]
                    vlist[w].prev = v.vid
                else:#原路徑長更小,沒有必要更新
                    pass
main()
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)

這里寫圖片描述

運行結(jié)果與數(shù)據(jù)變化表的最終情況一致。

得到最短路徑

把以下代碼和以上代碼合起來就可以運行成功,使用遞歸的思想來做:

def real_get_traj(start,index):
    traj_list = []
    def get_traj(index):#參數(shù)是頂點在vlist中的索引
        if(index == start):#終點
            traj_list.append(index)
            print(traj_list[::-1])#反轉(zhuǎn)list
            return
        if(vlist[index].dist == float('inf')):
            print('從起點到該頂點根本沒有路徑')
            return
        traj_list.append(index)
        get_traj(vlist[index].prev)
    get_traj(index)
    print('該最短路徑的長度為',vlist[index].dist)

real_get_traj(1,3)
real_get_traj(1,6)

這里寫圖片描述

如圖所示,從v1到v3的最短路徑為:[1, 4, 3]
從v1到v6的最短路徑為:[1, 4, 7, 6]

負權邊

這里寫圖片描述

Dijkstra算法要求邊上的權值不能為負數(shù),不然就會出錯。如上,本來最短路徑是012,但由于算法是貪心的,所以只會直接選擇到2

算法改進(若為無圈圖)

注意,只有有向無圈圖才有拓撲排序。

如果知道圖是無圈圖,那么我們可以通過改變聲明頂點為known的順序(原本這個順序是,每次從unknown里面找出個最小dist的頂點),或者叫做頂點選取法則,來改進Dijkstra算法。新法則以拓撲排序選擇頂點。由于選擇和更新(每次選擇和更新完成后,就會變成數(shù)據(jù)變化表中的某一種情況)可以在拓撲排序執(zhí)行的時候進行,因此算法能一趟完成。

因為當一個頂點v被選取以后,按照拓撲排序的法則它肯定沒有任何unknown頂點到v(指明方向)的入邊,因為v的距離 d v d_v dv?不可能再下降了(因為根本沒有別的路到v了),所以這種選擇方法是可行的。

使用這種方法不需要優(yōu)先隊列。

到此這篇python3實現(xiàn)Dijkstra算法最短路徑的文章就介紹到這了,更多最短路徑算法內(nèi)容請搜索W3Cschool以前的文章或繼續(xù)瀏覽下面的相關文章。


0 人點贊