從分支限界的角度來看Dijkstra算法：

Dijkstra算法是基于貪心的廣度優(yōu)先搜索，也可以看成分支限界法，從分支限界的角度來看，Dijkstra算法看起來就更加清晰明了

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

# ============================================================================= # 分支限界法，dijkstra算法 # 首先解空間[起點(diǎn)0，頂點(diǎn)1，當(dāng)點(diǎn)2，...,頂點(diǎn)n-1]看成[起點(diǎn)，剩余n-1個(gè)頂點(diǎn)的排列樹] # 下界函數(shù)bound()是什么了? # 可以參考貨郎問題：下屆為 已走過的路+未走過的路（未走過的結(jié)點(diǎn)的最小出邊和） # 同時(shí)我們可以優(yōu)化下界函數(shù)，我們知道起點(diǎn)到最后一個(gè)頂點(diǎn)的最短距離，那么他途徑得的頂點(diǎn) # 都是最短距離，那么我們可以把頂點(diǎn)到起點(diǎn)的最短距離當(dāng)作下界 # =============================================================================import heapq def dijkstra(graph,start):# 解空間的長度vnum = len(graph)# 優(yōu)先級(jí)隊(duì)列pqueue = []# 把起點(diǎn)放入隊(duì)列，[頂點(diǎn)到起點(diǎn)的距離，前驅(qū)結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)]heapq.heappush(pqueue,(0.0,None,start))# 有兩個(gè)用途：一是用來標(biāo)記那些頂點(diǎn)已經(jīng)訪問了，二是用于存儲(chǔ)前驅(qū)結(jié)點(diǎn)，用于解的追蹤# 在這里為什么可以用它標(biāo)記已訪問的結(jié)點(diǎn)和追蹤解，實(shí)際上這種貪心策略，已經(jīng)保證到底時(shí)，就# 可以得到最優(yōu)解了，一般的限界分支，可能還需要跑到離root很近的結(jié)點(diǎn)再往下走，每個(gè)結(jié)點(diǎn)# 需要記錄前驅(qū)結(jié)點(diǎn)和已訪問的結(jié)點(diǎn)。 paths = {vertex : None for vertex in graph}# depth可以放在活結(jié)點(diǎn)里depth = 0# 循環(huán)體出口時(shí)是解滿了，之前看起來很神奇的出口，現(xiàn)在就看起來很平常了while depth < vnum :# 彈出結(jié)點(diǎn)pair = heapq.heappop(pqueue)distance = pair[0]parent = pair[1]vertex = pair[2]# 加入結(jié)點(diǎn)已經(jīng)訪問過了，就直接彈出下一個(gè)結(jié)點(diǎn)if paths[vertex]:continue# 把該節(jié)點(diǎn)到起點(diǎn)的最短距離和前驅(qū)結(jié)點(diǎn)保存起來，并記錄該節(jié)點(diǎn)已經(jīng)訪問過了paths[vertex] = (parent,distance)# 把該節(jié)點(diǎn)的子節(jié)點(diǎn)放入優(yōu)先級(jí)隊(duì)列，這里進(jìn)行了剪枝，只放入和當(dāng)前結(jié)點(diǎn)相連的結(jié)點(diǎn)# 不相連的結(jié)點(diǎn)，認(rèn)為距離為無窮，沒有必要放入到優(yōu)先級(jí)隊(duì)列# 以下是相連的邊的終點(diǎn)頂點(diǎn)，把他們放入優(yōu)先級(jí)隊(duì)列edges = graph[vertex]for v in edges:# 加入終結(jié)點(diǎn)已經(jīng)訪問過，就沒有必要加入，這是一個(gè)排列樹if paths[v] is None:# 把這個(gè)頂點(diǎn)到起點(diǎn)的距離，這個(gè)結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)加入隊(duì)列，# 這個(gè)頂點(diǎn)到起點(diǎn)的距離：源節(jié)點(diǎn)的最短距離+他們的邊的長度heapq.heappush(pqueue,(distance + graph[vertex][v],vertex,v))# 進(jìn)入下一層，這個(gè)策略由于上面的continue保證了，每次到這兒可以進(jìn)入下一層了，# 也可以把depth放到活結(jié)點(diǎn)里，放到活結(jié)點(diǎn)，就必須要注意循環(huán)體的退出depth += 1return pathsg = {'A':{'B':1,'C':2},'B':{'A':1,'C':3,'D':4},'C':{'A':2,'B':3,'D':5,'E':6},'D':{'B':4,'C':5,'E':7,'F':8},'E':{'C':6,'D':7,'G':9},'F':{'D':8},'G':{'E':9}}t=dijkstra(g,'A') print(t)runfile('D:/share/test/dijkstra_prune.py', wdir='D:/share/test') {'A': (None, 0.0), 'B': ('A', 1.0), 'C': ('A', 2.0), 'D': ('B', 5.0), 'E': ('C', 8.0), 'F': ('D', 13.0), 'G': ('E', 17.0)}

總結(jié)

以上是生活随笔為你收集整理的分支限界发：Dijkstra算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。