具有优先级队列的 Dijkstra (Python)

Question

我一直在尝试在 Python 中使用 Dijkstra 算法实现优先级队列和距离表。

这是优先队列的实现：

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) < 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()

这是结果：

Traceback (most recent call last):

  File "dijkstra.py", line 76, in <module>

    shortest_path(g, 0, 6)

  File "dijkstra.py", line 46, in shortest_path

    distance_table = build_distance_table(graph, source)

  File "dijkstra.py", line 23, in build_distance_table

    while len(priority_queue.keys()) > 0:

AttributeError: 'numpy.float64' object has no attribute 'keys'

我正在使用 Python 3.7。我在网上搜索过，虽然它与 Python 版本有关。无法弄清楚为什么它看不到该属性。你能告诉我我错过了什么吗？

Answer 1

priority_queue = distance本来应该：priority_queue[neighbor] = distance解决了，谢谢