宇智波一打七今天學習了一個新算法，迫不及待和大家分享一下 。假裝是自己敲的
(直接從一打七的部落格截圖過來，溜)
優美的代碼來了
import heapqclass graph: def __init__(self,num,ma): self.edge={} self.dic=[ma]*(num+1) def add(self,u,v,w): if u in self.edge: self.edge[u].append((v,w)) else: self.edge[u]=[(v,w)] def dijkstra(self,start): dis=self.dic dis[start]=0 heap=[] visit=[0 for i in range(len(dis))] for i in self.edge[start]: dis[i[0]]=i[1] heapq.heappush(heap,(i[1],i[0]))# i[1]為該邊權值，i[0]為該點，從start點到其餘點的邊入堆 while heap!=[]: vic=heapq.heappop(heap)# 彈出最小邊 if visit[vic[1]]==1:# 如果該點已經彈出過，則不再松弛 continue visit[vic[1]] = 1# 記錄彈出點 if vic[1] not in self.edge:# 防止有向圖中出度為0的點 continue for i in self.edge[vic[1]]: if dis[i[0]]>dis[vic[1]]+i[1]:# 判斷是否松弛 dis[i[0]]=dis[vic[1]]+i[1]# 松弛邊 heapq.heappush(heap,(i[1],i[0]))# 松弛過邊則把新邊權值入堆 self.dic=dis def printf(self): print(self.dic[1:])if __name__ == "__main__": n,m=6,8 nums = [[1,3,10],[1,5,30],[1,6,100],[2,3,5],[3,4,50],[4,6,10],[5,6,60],[5,4,20]] g=graph(n,1000000000000) for i in nums: g.add(i[0],i[1],i[2]) g.dijkstra(1) g.printf()
我們在算法第二步求最小的點時可用堆做優化。在python中有子產品heapq，這裡我們直接使用該子產品的最小堆即可。
注意：dijkstra算法不能求解有負權邊的圖(思考一下為什麼？)。
才不告訴你一打七是為了練習python的面向對象。