Dijkstra + heap (self implementation)

Question

Cheers guys. Learning datastructures and algorithms atm.

I wrote heapq and dijkstra. And seems like they both works separatly (I tested heapq with some values, and dijkstra with builtin priorityqueue and heapq on different graphs).

But together mine implementation of heapq doesnt work with dijkstra. For any reason dijkstra returns randomly paved path (sometimes it's actually right), so I cant figure out why it so. Would be very glad for any hint!

Heap

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

Dijkstra + heap (self implementation)

Answers (1)

Related Questions