Python의 우선 순위 대기열을 사용하는 Dijkstra의 알고리즘에서 대상 노드 찾기

Question

나는이 인접성 목록을 사용하여 그래프를 구현했으며 Dijkstra 's Algorithm과 함께 작동시키고 싶습니다. 나는 두뇌가 죽었는지 아닌지 모르지만 우선 순위 큐 버전을 소스에서 시작까지의 최단 경로를 찾는 방법을 생각할 수는 없습니다. 위키 피 디아 페이지를 읽었지만 충분하지 않습니다. 아무도 도와 줄 수 있니?!

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.