title: Finding a Target node on Dijkstra’s Algorithm with Priority Queues in Python
body: <p>I have this implementation of a graph using adjacency lists and I want to make it work with Dijkstra’s Algorithm. I don't know whether I'm brain dead or not but I can't think of a way to make the priority queue version find the shortest path from the source to the start. I've read the wikipedia page but it just isn't enough. Can anybody help?!</p>
  
  <pre><code>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 &lt; nextVert.getDistance():
                  nextVert.setDistance( newDist )
                  nextVert.setPred(currentVert)
                  pq.decreaseKey(nextVert,newDist)
  </code></pre>