在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。