溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
今天小編給大家分享一下python3怎么實現Dijkstra算法最短路徑的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。
問題：根據每條邊的權值，求出從起點s到其他每個頂點的最短路徑和最短路徑的長度。
說明：不考慮權值為負的情況，否則會出現負值圈問題。
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 < d w d_v+c_{v,w}<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
現在我們能找到起點 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的第四行，發現 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是起點，結束。 v 3 v_3 v3上一個是 v 4 v_4 v4， v 4 v_4 v4上一個是 v 1 v_1 v1，反過來就得到了最短路徑 v 1 = > v 4 = > v 3 v_1=>v_4=>v_3 v1=>v4=>v3
上述分析，其實就是求最短路徑的算法的思想：在對每個頂點對象進行處理后變成數據變化表的最終情況后，可以通過對任意頂點 v i v_i vi的 p v p_v pv值，回溯得到反轉的最短路徑。
紙上得來終覺淺，絕知此事要躬行！使用python3來實現功能。
本文提到，將使用優先隊列來實現尋找未知頂點中，具有最小dist的頂點。使用python已有實現好的優先隊列。但實驗中報錯如下：
意思，Vertex實例并不支持小于比較運算符。所以需要實現Vertex類的__lt__方法。下面科普一下：
| 方法名 | 比較運算符 | 含義 |
|---|---|---|
__eq__ | == | equal |
__lt__ | < | less than |
__le__ | <= | less and equal |
__gt__ | > | greater than |
__ge__ | >= | greater and equal |
但很遺憾，python庫自帶的優先隊列from queue import PriorityQueue，并不滿足本文的需求。當PriorityQueue的元素為對象時，需要該對象的class實現__lt__函數，在往優先隊列里添加元素時，內部是用的堆排序，堆排序的特點為每個堆（以及每個子堆）的第一個元素總是那個最小的元素。關鍵在于，在建立了這個堆后，堆就已經記錄下來了創建堆時各個元素的大小關系了，在創建優先隊列后，再改變某個對象的值，這個堆的結構是肯定不會變的，所以這種堆排序造成了排序是一次性的，如果之后某個對象的屬性發生變化，堆的結構也不會隨之而改變。
或者說，我們想要的優先隊列肯定不是系統提供的優先隊列，因為我們要支持可變對象的成員修改導致堆的改變，解決方案有三種，1.內部使用的堆排序的堆，最起碼要支持，刪除任意節點和增加節點操作（因為這兩步就可以達到修改的效果了）2.這個內部堆，在執行出隊操作時，考察哪個節點有修改操作，再把堆改變到正確的形態，再出隊3.維護一個list，進行排降序，然后每改變一個可變對象的值，就對這個對象進行冒泡或者二分查找找到位置（因為別的都是已經排好序的了，只有它不在正確的位置），最后再list.pop()，但第三個方案是我后來想到的，所以下面代碼并不是這樣實現的，讀者可以進行嘗試，肯定比每次遍歷全部快。
應該說，可能用不上隊列了。我們可能只需要一個list或者set來存儲v，在出隊前隨便vi改變其dist，在出隊時再遍歷找到最小的dist的vi，再刪除掉這個vi即可。因為vi的dist一直在變，需求特殊，但是沒必要專門造個輪子（感覺這個輪子也不好造），雖然時間復雜度可能高了點，但代碼簡單了啊。
失效代碼如下：三個節點對象的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)#結果為vid: 1而如果將在入隊前，就把dist改變了，就能正確的出隊。
v3.dist = 0
for i in range(0,len(vlist)):
q.put(vlist[i])
#結果為vid: 3class 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)
#創建頂點對象
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)
#創建一個長度為8的數組，來存儲頂點，0索引元素不存
vlist = [False,v1,v2,v3,v4,v5,v6,v7]
#使用set代替優先隊列，選擇set主要是因為set有方便的remove方法
vset = set([v1,v2,v3,v4,v5,v6,v7])
def get_unknown_min():#此函數則代替優先隊列的出隊操作
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
#此時已經找到了未知的最小的元素是誰
vset.remove(vlist[the_index])#相當于執行出隊操作
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)運行結果與數據變化表的最終情況一致。
把以下代碼和以上代碼合起來就可以運行成功，使用遞歸的思想來做：
def real_get_traj(start,index):
traj_list = []
def get_traj(index):#參數是頂點在vlist中的索引
if(index == start):#終點
traj_list.append(index)
print(traj_list[::-1])#反轉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算法要求邊上的權值不能為負數，不然就會出錯。如上，本來最短路徑是012，但由于算法是貪心的，所以只會直接選擇到2
注意，只有有向無圈圖才有拓撲排序。
如果知道圖是無圈圖，那么我們可以通過改變聲明頂點為known的順序（原本這個順序是，每次從unknown里面找出個最小dist的頂點），或者叫做頂點選取法則，來改進Dijkstra算法。新法則以拓撲排序選擇頂點。由于選擇和更新（每次選擇和更新完成后，就會變成數據變化表中的某一種情況）可以在拓撲排序執行的時候進行，因此算法能一趟完成。
因為當一個頂點v被選取以后，按照拓撲排序的法則它肯定沒有任何unknown頂點到v（指明方向）的入邊，因為v的距離 d v d_v dv不可能再下降了（因為根本沒有別的路到v了），所以這種選擇方法是可行的。
使用這種方法不需要優先隊列。
以上就是“python3怎么實現Dijkstra算法最短路徑”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
