title: Dijkstra with a Priority Queue (Python)
body: <p>I have been trying to use Dijkstra's algorithm with an implementation of a priority queue and a distance table, in Python.</p>
  <p>This is the priority queue implementation:</p>
  <pre><code>from heapq import heapify, heappush, heappop
  
  class priority_dict(dict):
  
      def __init__(self, *args, **kwargs):
          super(priority_dict, self).__init__(*args, **kwargs)
          self._rebuild_heap()
  
      def _rebuild_heap(self):
          self._heap = [(v, k) for k, v in self.items()]
          heapify(self._heap)
  
      def smallest(self):
          heap = self._heap
          v, k = heap[0]
          while k not in self or self[k] != v:
              heappop(heap)
              v, k = heap[0]
          return k
  
      def pop_smallest(self):
          heap = self._heap
          v, k = heappop(heap)
          while k not in self or self[k] != v:
              v, k = heappop(heap)
          del self[k]
          return k
  
      def __setitem__(self, key, val):
          super(priority_dict, self).__setitem__(key, val)
          
          if len(self._heap) &lt; 2 * len(self):
              heappush(self._heap, (val, key))
          else:
              self._rebuild_heap()
  
      def setdefault(self, key, val):
          if key not in self:
              self[key] = val
              return val
          return self[key]
  
      def update(self, *args, **kwargs):
          super(priority_dict, self).update(*args, **kwargs)
          self._rebuild_heap()
  
      def sorted_iter(self):
          while self:
              yield self.pop_smallest()
  </code></pre>
  <p>And this is the Dijkstra implementation:</p>
  <pre><code>import priority_dict
  
  from graph import *
  
  def build_distance_table(graph, source):
      distance_table = {}
  
      for i in range(graph.numVertices):
          distance_table[i] = (None, None)
  
      distance_table[source] = (0, source)
  
      priority_queue = priority_dict.priority_dict()
  
      priority_queue[source] = 0
  
      while len(priority_queue.keys()) &gt; 0:
          current_vertex = priority_queue.pop_smallest()
  
          current_distance = distance_table[current_vertex][0]
  
          for neighbor in graph.get_adjacent_vertices(current_vertex):
              distance = current_distance + g.get_edge_weight(current_vertex, neighbor)
  
              neighbor_distance = distance_table[neighbor][0]
  
              if neighbor_distance is None or neighbor_distance &gt; distance:
                  distance_table[neighbor] = (distance, current_vertex)
  
                  priority_queue = distance
  
      return distance_table
  
  def shortest_path(graph, source, destination):
      distance_table = build_distance_table(graph, source)
  
      path = [destination]
  
      previous_vertex = distance_table[destination][1]
  
      while previous_vertex and previous_vertex is not source:
          path = [previous_vertex] + path
  
          previous_vertex = distance_table[previous_vertex][1]
      
      if previous_vertex is None:
          print(&quot;There is no path from %d to %d&quot; % (source, destination))
      else:
          path: [source] + path
          print(&quot;Shortest path is: &quot;, path)
  </code></pre>
  <p>This is the result:</p>
  <pre><code>Traceback (most recent call last):
    File &quot;dijkstra.py&quot;, line 76, in &lt;module&gt;
      shortest_path(g, 0, 6)
    File &quot;dijkstra.py&quot;, line 46, in shortest_path
      distance_table = build_distance_table(graph, source)
    File &quot;dijkstra.py&quot;, line 23, in build_distance_table
      while len(priority_queue.keys()) &gt; 0:
  AttributeError: 'numpy.float64' object has no attribute 'keys'
  </code></pre>
  <p>I am using Python 3.7. I have searched online and though it had to do with the Python version. Can't figure why it doesn't see the attribute. Could you please tell me what am I missing?</p>