宇智波一打七今天学习了一个新算法，迫不及待和大家分享一下 。假装是自己敲的
(直接从一打七的博客截图过来，溜)
优美的代码来了
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的面向对象。