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

Dijkstra

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]