在Python中使用优先队列在Dijkstra算法上寻找目标节点

Question

我有使用邻接列表的图的实现，我想使它与Dijkstra的算法一起工作。我不知道自己是否脑死亡，但我想不出让优先队列版本找到从源到最短的最短路径。我已经阅读了维基百科页面，但这还不够。任何人都可以帮忙吗？！

class Vertex: 
def __init__(self,key): 
    self.id = key 
    self.connectedTo = {} 

def addNeighbor(self,nbr,weight=0): 
    self.connectedTo[nbr] = weight 

def __str__(self): 
    return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo]) 

def getConnections(self): 
    return self.connectedTo.keys() 

def getId(self): 
    return self.id 

def getWeight(self,nbr): 
    return self.connectedTo[nbr] 

class Graph: 
def __init__(self): 
    self.vertList = {} 
    self.numVertices = 0 

def addVertex(self,key): 
    self.numVertices = self.numVertices + 1 
    newVertex = Vertex(key) 
    self.vertList[key] = newVertex 
    return newVertex 

def getVertex(self,n): 
    if n in self.vertList: 
     return self.vertList[n] 
    else: 
     return None 

def __contains__(self,n): 
    return n in self.vertList 

def addEdge(self,f,t,cost=0): 
    if f not in self.vertList: 
     nv = self.addVertex(f) 
    if t not in self.vertList: 
     nv = self.addVertex(t) 
    self.vertList[f].addNeighbor(self.vertList[t], cost) 

def getVertices(self): 
    return self.vertList.keys() 

def __iter__(self): 
    return iter(self.vertList.values()) 

def main(self, input1): 
      """ 
      Automates the insertion process 
      """ 
      try: 
       if input1 is None: 
        ans=True 
        while ans != False: 
         print (""" 
         1.Insert nodes 
         2.Print representation 
         3.Exit 
         """) 
         ans=input("What would you like to do?") 
         if ans=="1": 
          rfilename = input("Enter file to read: ") 
          f = open(rfilename) #file 1 
          linelist = list(f) #linelist is a list with each member corresponding to one line in the txt file 
          for i in range(len(linelist)): #inserts all vertexes 
           line = linelist[i].split() 
           self.addVertex(line[0]) 
          for i in range(len(linelist)): #inserts all edges 
           line = linelist[i].split() 
           self.addEdge(line[0], line[1], int(line[2])) 
         elif ans=="2": 
          for v in self: 
           for w in v.getConnections(): 
            print("(%s to %s, %s)" % (v.getId(), w.getId(), v.getWeight(w))) 
         elif ans=="3": 
          ans = False 

      except(FileNotFoundError): 
         print("File not found") 

def dijkstra(self,start): 
    pq = PriorityQueue() 
    start.setDistance(0) 
    pq.insert([(v.getDistance(),v) for v in self]) 
    while not pq.is_empty(): 
     currentVert = pq.remove() 
     for nextVert in currentVert.getConnections(): 
      newDist = currentVert.getDistance() + currentVert.getWeight(nextVert) 
      if newDist < nextVert.getDistance(): 
       nextVert.setDistance(newDist) 
       nextVert.setPred(currentVert) 
       pq.decreaseKey(nextVert,newDist) 

Answer 1

基于Python Algorithms书“马格努斯烈赫特兰”你可以做到这一点优雅与heapg模块。该模块提供了堆队列算法的实现，也称为优先级队列算法。

from heapq import heappush, heappop 
def dijkstra(G, s): 
    D, P, Q, S = {s:0}, {}, [(0,s)], set() #Est., tree, queue, visited 
    while Q:         #Still unprocessed nodes? 
     _, u = heappop(Q)      #Node with lowest estimate 
     if u in S: continue     #Already visited? Skip it 
      S.add(u)       #We've visited it now 
      for v in G[u]:     #Go through all its neighbors 
       relax(G, u, v, D, P)   #Relax the out-edge 
       heappush(Q, (D[v], v))  #Add to queue, w/est. as pri 
    return D, P        #Final D and P returned 

Dijkstra’s algorithm可能类似于普里姆的（与另一组队列优先级），但它是 也是密切相关的另一个老最喜欢的：BFS。