問(wèn)題描述

現(xiàn)有一個(gè)有向賦權(quán)圖。如下圖所示：

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

問(wèn)題分析

Dijkstra算法按階段進(jìn)行，同無(wú)權(quán)最短路徑算法（先對(duì)距離為0的頂點(diǎn)處理，再對(duì)距離為1的頂點(diǎn)處理，以此類(lèi)推）一樣，都是先找距離最小的。
在每個(gè)階段，Dijkstra算法選擇一個(gè)頂點(diǎn)v，它在所有unknown頂點(diǎn)中具有最小的 d v d_v dv​，同時(shí)算法聲明從s到v的最短路徑是known的。階段的其余部分為，對(duì)w的 d v d_v dv​（距離）和 p v p_v pv​（上一個(gè)頂點(diǎn)）更新工作（當(dāng)然也可能不更新）。
在算法的每個(gè)階段，都是這樣處理的：
【0.5】在無(wú)權(quán)的情況下，若 d w d_w dw​= ∞ \infty ∞則置 d w = d v + 1 d_w=d_v+1 dw​=dv​+1（無(wú)權(quán)最短路徑）
【1】在有權(quán)的情況下，若 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 ∞，開(kāi)始分析：從頂點(diǎn)v到頂點(diǎn)w的路徑，若能使得w的路徑長(zhǎng)比w原來(lái)的路徑長(zhǎng)短一點(diǎn)，那么就需要對(duì)w進(jìn)行更新，否則不對(duì)w更新。即滿足 d v + c v , w &lt; d w d_v+c_{v,w}&lt;d_w dv​+cv,w​<dw​時(shí)，就需要把 d w d_w dw​的值更新為 d v + c v , w d_v+c_{v,w} dv​+cv,w​，同時(shí)頂點(diǎn)w的 p v p_v pv​值得改成頂點(diǎn)v

實(shí)現(xiàn)過(guò)程

考慮Dijkstra算法過(guò)程中，有一個(gè)數(shù)據(jù)變化表。

初始狀態(tài)如上。開(kāi)始頂點(diǎn)s是 v 1 v_1 v1​，所有頂點(diǎn)都是unknown的。 v 1 v_1 v1​的 d v d_v dv​的值為0，因?yàn)樗瞧瘘c(diǎn)。

【1】選擇unknown頂點(diǎn)中， d v d_v dv​值最小的頂點(diǎn)，即頂點(diǎn) v 1 v_1 v1​。首先將 v 1 v_1 v1​標(biāo)記為known。對(duì)與 v 1 v_1 v1​鄰接的頂點(diǎn) v 2 v 4 v_2 v_4 v2​v4​進(jìn)行調(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​；同理，對(duì) v 4 v_4 v4​作相應(yīng)的處理。

【2】選擇unknown頂點(diǎn)中， d v d_v dv​值最小的頂點(diǎn)，即頂點(diǎn) v 4 v_4 v4​（其距離為1，最小）。將 v 4 v_4 v4​標(biāo)記為known。對(duì)其鄰接的頂點(diǎn) v 3 v 5 v 6 v 7 v_3 v_5 v_6 v_7 v3​v5​v6​v7​作相應(yīng)的處理。

【3】選擇unknown頂點(diǎn)中， d v d_v dv​值最小的頂點(diǎn)，即頂點(diǎn) v 2 v_2 v2​（其距離為2，最?。?v 2 v_2 v2​標(biāo)記為known。對(duì)其鄰接的頂點(diǎn) v 4 v 5 v_4v_5 v4​v5​作相應(yīng)的處理。但 v 4 v_4 v4​是已知的，所以不需要調(diào)整；因?yàn)榻?jīng)過(guò) 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，所以也不需要也沒(méi)有必要調(diào)整。

【4】選擇unknown頂點(diǎn)中， d v d_v dv​值最小的頂點(diǎn)，即頂點(diǎn) v 5 v_5 v5​（距離為3，最小，其實(shí)還有 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​的運(yùn)行結(jié)果都是一樣的）。將 v 5 v_5 v5​標(biāo)記為known。對(duì)其鄰接的頂點(diǎn) v 7 v_7 v7​作相應(yīng)的處理。但原路徑長(zhǎng)更小，所以不用調(diào)整。

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

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

【7】最后，再對(duì) v 6 v_6 v6​處理。不需調(diào)整。

上述實(shí)現(xiàn)過(guò)程對(duì)應(yīng)的算法，可能需要用到優(yōu)先隊(duì)列，每次出隊(duì) d v d_v dv​值最小的頂點(diǎn)，因?yàn)槿绻皇潜闅v來(lái)找到 d v d_v dv​值最小的頂點(diǎn)，可能會(huì)花費(fèi)很多時(shí)間。

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

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

現(xiàn)在我們能找到起點(diǎn) v 1 v_1 v1​到任意的 v i v_i vi​（除了起點(diǎn)）的最短路徑，及其最短路徑長(zhǎng)。
比如，找到 v 1 v_1 v1​到 v 3 v_3 v3​的最短路徑。
【1】 v 3 v_3 v3​的 d v d_v dv​值為3，所以最短路徑長(zhǎng)為3
【2】 v 3 v_3 v3​的 p v p_v pv​值為 v 4 v_4 v4​，所以 v 3 v_3 v3​的上一個(gè)頂點(diǎn)為 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​的上一個(gè)頂點(diǎn)為 v 1 v_1 v1​
【4】 v 1 v_1 v1​是起點(diǎn)，結(jié)束。 v 3 v_3 v3​上一個(gè)是 v 4 v_4 v4​， v 4 v_4 v4​上一個(gè)是 v 1 v_1 v1​，反過(guò)來(lái)就得到了最短路徑 v 1 = &gt; v 4 = &gt; v 3 v_1=&gt;v_4=&gt;v_3 v1​=>v4​=>v3​
上述分析，其實(shí)就是求最短路徑的算法的思想：在對(duì)每個(gè)頂點(diǎn)對(duì)象進(jìn)行處理后變成數(shù)據(jù)變化表的最終情況后，可以通過(guò)對(duì)任意頂點(diǎn) v i v_i vi​的 p v p_v pv​值，回溯得到反轉(zhuǎn)的最短路徑。

代碼實(shí)現(xiàn)

紙上得來(lái)終覺(jué)淺，絕知此事要躬行！使用python3來(lái)實(shí)現(xiàn)功能。
本文提到，將使用優(yōu)先隊(duì)列來(lái)實(shí)現(xiàn)尋找未知頂點(diǎn)中，具有最小dist的頂點(diǎn)。使用python已有實(shí)現(xiàn)好的優(yōu)先隊(duì)列。但實(shí)驗(yàn)中報(bào)錯(cuò)如下：

意思，Vertex實(shí)例并不支持小于比較運(yùn)算符。所以需要實(shí)現(xiàn)Vertex類(lèi)的__lt__方法。下面科普一下：

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

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

應(yīng)該說(shuō)，可能用不上隊(duì)列了。我們可能只需要一個(gè)list或者set來(lái)存儲(chǔ)v，在出隊(duì)前隨便vi改變其dist，在出隊(duì)時(shí)再遍歷找到最小的dist的vi，再刪除掉這個(gè)vi即可。因?yàn)関i的dist一直在變，需求特殊，但是沒(méi)必要專(zhuān)門(mén)造個(gè)輪子（感覺(jué)這個(gè)輪子也不好造），雖然時(shí)間復(fù)雜度可能高了點(diǎn)，但代碼簡(jiǎn)單了啊。

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

失效代碼如下：三個(gè)節(jié)點(diǎn)對(duì)象的dist都是無(wú)窮大，在三個(gè)對(duì)象都進(jìn)入隊(duì)列，再把v3的dist改成0，想要的效果是出隊(duì)出v3，但出隊(duì)出的是v1。原因如上：

from queue import PriorityQueue
class Vertex:
    #頂點(diǎn)類(lèi)
    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

而如果將在入隊(duì)前，就把dist改變了，就能正確的出隊(duì)。

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

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

class Vertex:
    #頂點(diǎn)類(lèi)
    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)為無(wú)窮大
        self.prev = 0#上一個(gè)頂點(diǎn)的id，默認(rèn)為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)建頂點(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])
#存儲(chǔ)邊的權(quán)值
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)建一個(gè)長(zhǎng)度為8的數(shù)組，來(lái)存儲(chǔ)頂點(diǎn)，0索引元素不存
vlist = [False,v1,v2,v3,v4,v5,v6,v7]
#使用set代替優(yōu)先隊(duì)列，選擇set主要是因?yàn)閟et有方便的remove方法
vset = set([v1,v2,v3,v4,v5,v6,v7])

def get_unknown_min():#此函數(shù)則代替優(yōu)先隊(duì)列的出隊(duì)操作
    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
    #此時(shí)已經(jīng)找到了未知的最小的元素是誰(shuí)
    vset.remove(vlist[the_index])#相當(dāng)于執(zhí)行出隊(duì)操作
    return vlist[the_index]

def main():
    #將v1設(shè)為頂點(diǎn)
    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:#原路徑長(zhǎng)更小，沒(méi)有必要更新
                    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)

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

得到最短路徑

把以下代碼和以上代碼合起來(lái)就可以運(yùn)行成功，使用遞歸的思想來(lái)做：

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

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

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

負(fù)權(quán)邊

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

算法改進(jìn)（若為無(wú)圈圖）

注意，只有有向無(wú)圈圖才有拓?fù)渑判颉?/p>

如果知道圖是無(wú)圈圖，那么我們可以通過(guò)改變聲明頂點(diǎn)為known的順序（原本這個(gè)順序是，每次從unknown里面找出個(gè)最小dist的頂點(diǎn)），或者叫做頂點(diǎn)選取法則，來(lái)改進(jìn)Dijkstra算法。新法則以拓?fù)渑判蜻x擇頂點(diǎn)。由于選擇和更新（每次選擇和更新完成后，就會(huì)變成數(shù)據(jù)變化表中的某一種情況）可以在拓?fù)渑判驁?zhí)行的時(shí)候進(jìn)行，因此算法能一趟完成。

因?yàn)楫?dāng)一個(gè)頂點(diǎn)v被選取以后，按照拓?fù)渑判虻姆▌t它肯定沒(méi)有任何unknown頂點(diǎn)到v（指明方向）的入邊，因?yàn)関的距離 d v d_v dv​不可能再下降了（因?yàn)楦緵](méi)有別的路到v了），所以這種選擇方法是可行的。

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

到此這篇關(guān)于python3實(shí)現(xiàn)Dijkstra算法最短路徑的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)python3 最短路徑內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論