python - Dijkstra + 堆(自行实现)

Question

干杯，伙计们。 学习数据结构和算法atm。

我写了 heapq 和 dijkstra。似乎它们都是分开工作的(我用一些值测试了 heapq，并在不同的图上测试了带有内置优先级队列和 heapq 的 dijkstra)。

但是我的 heapq 实现不能与 dijkstra 一起使用。无论出于何种原因，dijkstra 返回随机铺好的路径(有时实际上是正确的)，所以我无法弄清楚为什么会这样。任何提示都会非常高兴!

堆

class MinHeap:
    
    def __init__(self, capacity):
        self.arr = [(float('inf'), -1)] * capacity
        self.capacity = capacity
        self.size = 0
        
    def get_parent_index(self, index):
        return (index -1) // 2
        
    def get_left_child(self, index):
        return 2 * index + 1
        
    def get_right_child(self, index):
        return 2 * index + 2
        
    def has_parent(self, index):
        return self.get_parent_index(index) >= 0
        
    def has_left_child(self, index):
        return self.get_left_child(index) < self.size
    
    def has_right_child(self, index):
        return self.get_right_child(index) < self.size
        
    def parent(self, index):
        return self.arr[self.get_parent_index(index)]
        
    def left_child(self, index):
        return self.arr[self.get_left_child(index)]
        
    def right_child(self, index):
        return self.arr[self.get_right_child(index)]
            
    def swap(self, ind1, ind2):
        self.arr[ind1], self.arr[ind2] = self.arr[ind2], self.arr[ind1]
            
    def insert(self, data):
        self.arr[self.size] = data
        self.size += 1
        self.up()
        
    def remove(self):
        if self.arr:
            data = self.arr[0]
            self.arr[0] = self.arr.pop()
            self.size -=1
            self.down()
            return data
        
    def up(self):
        index = self.size -1
        while (self.has_parent(index) and self.parent(index)[0] > self.arr[index][0]):
            self.swap(self.get_parent_index(index), index)
            index = self.get_parent_index(index)
            
    def down(self):
        index = 0
        while self.has_left_child(index):
            smallest = self.get_left_child(index)
            if (self.has_right_child(index) and self.right_child(index)[0] < self.left_child(index)[0]):
                smallest = self.get_right_child(index)
            if self.arr[index][0] < self.arr[smallest][0]:
                break
            else:
                self.swap(index, smallest)
            index = smallest

迪杰斯特拉

def dijkstra(G, start, goal):
    visited = set()
    cost = {start: 0}
    parent = {start: None}
    todo = MinHeap(len(G))
    todo.insert((0, start))
    while todo:
        while todo:
            _, vertex = todo.remove()
            if vertex not in visited: break
        else: break
            
        visited.add(vertex)
        if vertex == goal: break
        for neighbor, distance in G[vertex]:
            if neighbor in visited: continue
            old_cost = cost.get(neighbor, float('inf')) 
            new_cost = cost[vertex] + distance
            if new_cost < old_cost:
                todo.insert((new_cost, neighbor))
                cost[neighbor] = new_cost
                parent[neighbor] = vertex
    return parent

def make_path(parent, goal):
    if goal not in parent:
        return None
    v = goal
    path = []
    while v is not None: 
        path.append(v)
        v = parent[v]
    return path[::-1]


G = {
'a': { ('b', 6), ('c', 1) },
'b': { ('d', 4)},
'c': { ('b', 3), ('e',3)},
'd': {('f', 5)},
'e': {('d', 1)},
'f': { },
'z': {('c', 2)}
}

parent = dijkstra(G, 'a', 'f')
print(make_path(parent, 'f'))
print(dijkstra(G, 'a', 'f'))

Answer 1

您的堆实现有问题。一方面，它分配一个固定大小的数组，但另一方面，它对其执行 pop() 。这是矛盾的，并且使得 remove 方法将 inf 值与实际值混合。

因此更改这些行:

        self.arr[0] = self.arr.pop()
        self.size -=1

至:

        self.size -=1
        self.arr[0] = self.arr[self.size]