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

Question

我一直在尝试在 Python.

中使用 Dijkstra 算法实现优先级队列和距离 table

这是优先级队列的实现：

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

这是 Dijkstra 实现：

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()) > 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 > 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("There is no path from %d to %d" % (source, destination))
    else:
        path: [source] + path
        print("Shortest path is: ", path)

这是结果：

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

解决了，谢谢

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

Dijkstra with a Priority Queue (Python)

python

graph

queue

traversal

dijkstra