dijkstra迪杰斯特算法邻接表加二叉堆实现python版

dijkstra迪杰斯特算法

需要知道的点：
1、属于贪心算法
2、得到一点到其他各点的所有距离
3、需要用到所有的信息
4、图中不能有负数权重

dijkstra算法过程

今天不是铅笔加手写

python+优先队列实现（这里用的二叉堆）

def showGraph(linkList):for vert in linkList:for n in vert.getNeighbor():print("%s---邻接---%s--权重：%s"%(vert.getValue(),n,vert.getWightTo(n)))
class vertix:def __init__(self,v):self.value=vself.neighbor={}self.D=float("inf")def getValue(self):return  self.valuedef getNeighbor(self):return self.neighbor.keys()def addNeighbor(self,v,w):self.neighbor[v]=wdef getWightTo(self,v):return self.neighbor[v]def getD(self):return self.Ddef setD(self,newD):self.D=newDimport heapq
class dijkstra:def __init__(self,gragh):self.gragh=graghdef getMinPath(self,start):for i,node in enumerate(self.gragh):node.setD(2**32+i)self.gragh[start].setD(0)#创建二叉堆mydata=[[node.getD(),node.getValue()] for node in self.gragh]heapq.heapify(mydata)#优先队列中以D为键建立优先级while mydata:key,thisIndex=heapq.heappop(mydata)thisNode=self.gragh[thisIndex]for neibor in self.gragh[thisIndex].getNeighbor():self.gragh[neibor].setD(min(self.gragh[neibor].getD(),thisNode.getD()+thisNode.getWightTo(neibor)))tempData=[]for node in mydata:tempVer=self.gragh[node[1]]heapq.heappush(tempData,[tempVer.getD(),tempVer.getValue()])mydata=tempDatares=[]for ver in self.gragh:res.append(ver.getD())return resif __name__ == '__main__':    inputData=[[(1,12),(5,16),(6,14)],[(0,12),(2,10),(5,7)],[(1,10),(3,3),(4,5),(5,6)],[(2,3),(4,4)],[(2,5),(3,4),(5,2),(6,8)],[(0,16),(1,7),(2,6),(4,2),(6,9)],[(0,14),(4,8),(5,9)]] #构造邻接表linkList=[]for i in range(len(inputData)):thisVerix=vertix(i)for v,w in inputData[i]:thisVerix.addNeighbor(v,w)linkList.append(thisVerix)showGraph(linkList)myDijstrs=dijkstra(linkList)print("最终结果------->")print(myDijstrs.getMinPath(0))

运行结果

0---邻接---1--权重：12
0---邻接---5--权重：16
0---邻接---6--权重：14
1---邻接---0--权重：12
1---邻接---2--权重：10
1---邻接---5--权重：7
2---邻接---1--权重：10
2---邻接---3--权重：3
2---邻接---4--权重：5
2---邻接---5--权重：6
3---邻接---2--权重：3
3---邻接---4--权重：4
4---邻接---2--权重：5
4---邻接---3--权重：4
4---邻接---5--权重：2
4---邻接---6--权重：8
5---邻接---0--权重：16
5---邻接---1--权重：7
5---邻接---2--权重：6
5---邻接---4--权重：2
5---邻接---6--权重：9
6---邻接---0--权重：14
6---邻接---4--权重：8
6---邻接---5--权重：9
最终结果------->
[0, 12, 22, 22, 18, 16, 14]