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

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

dijkstra迪杰斯特算法

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

dijkstra算法过程

今天不是铅笔加手写

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

def showGraph(linkList):for vert in linkList:for n Neighbor():print("%s---邻接---%s--权重：%s"%(Value(),WightTo(n)))
class vertix:def __init__(self,v):self.value&#ighbor={}self.D=float("inf")def getValue(self):return  self.valuedef getNeighbor(self):ighbor.keys()def addNeighbor(self,v,w):ighbor[v]=wdef getWightTo(self,v):ighbor[v]def getD(self):return self.Ddef setD(self,newD):self.D=newDimport heapq
class dijkstra:def __init__(self,gragh):agh=graghdef getMinPath(self,start):for i,node in agh):node.setD(2**32+agh[start].setD(0)#创建二叉堆mydata=[[D(),Value()] for node agh]heapq.heapify(mydata)#优先队列中以D为键建立优先级while mydata:key,thisIndex=heapq.heappop(mydata)thisNode&#agh[thisIndex]for neibor agh[thisIndex].getNeighbor():agh[neibor].setD(agh[neibor].getD(),D()&#WightTo(neibor)))tempData=[]for node in mydata:tempVer&#agh[node[1]]heapq.heappush(tempData,[D(),Value()])mydata=tempDatares=[]for ver agh:res.D())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("最终结果------->")MinPath(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]