Алгоритм Дейкстры в python с использованием словарей

Question

Уважаемые любители информатики,

Я наткнулся на проблему при попытке реализовать алгоритм Дейкстры для определения кратчайшего пути между начальным узлом и всеми другими узлами в графе.

Если быть точным, я предоставлю вам столько фрагментов кода и информации, которые я считаю полезными для данного случая. Однако, если вы что-то пропустили, пожалуйста, дайте мне знать.

Я реализовал класс PQueue для обработки очередей приоритетов каждого отдельного узла, и он выглядит следующим образом:

class PQueue:
    def __init__(self):
        self.items = []

    def push(self, u, value):
        self.items.append((u, value))

        # insertion sort
        j = len(self.items) - 1
        while j > 0 and self.items[j - 1][1] > value:
            self.items[j] = self.items[j - 1]  # Move element 1 position backwards
            j -= 1
        # node u now belongs to position j
        self.items[j] = (u, value)

    def decrease_key(self, u, value):
        for i in range(len(self.items)):
            if self.items[i][0] == u:
                self.items[i][1] = value
                j = i
                break

        # insertion sort
        while j > 0 and self.items[j - 1][1] > value:
            self.items[j] = self.items[j - 1]  # Move element 1 position backwards
            j -= 1
        # node u now belongs to position j
        self.items[j] = (u, value)

def pop_min(self):
    if len(self.items) == 0:
        return None
    self.items.__delitem__(0)
    return self.items.index(min(self.items))

Если вы не совсем уверены в том, что такое алгоритм Дейкстры, вы можете обновить свои знания здесь . Теперь, чтобы перейти к актуальной проблеме, я объявил функцию dijkstra:

def dijkstra(self, start):
    # init
    totalCosts = {}  # {"node"= cost,...}
    prevNodes = {}  # {"node"= prevNode,...}
    minPQ = PQueue()  # [[node, cost],...]
    visited = set()

    # start init
    totalCosts[str(start)] = 0
    prevNodes[str(start)] = start
    minPQ.push(start, 0)

    # set for all other nodes cost to inf
    for node in range(self.graph.length):  # #nodes
        if node != start:
            totalCosts[str(node)] = np.inf

    while len(minPQ.items) != 0:  # Main loop
        # remove smallest item
        curr_node = minPQ.items[0][0]  # get index/number of curr_node
        minPQ.pop_min()
        visited.add(curr_node)

        # check neighbors
        for neighbor in self.graph.adj_list[curr_node]:
            # check if visited
            if neighbor not in visited:
                # check cost and put it in totalCost and update prev node
                cost = self.graph.val_edges[curr_node][neighbor]  # update cost of curr_node -> neighbor
                minPQ.push(neighbor, cost)
                totalCosts[str(neighbor)] = cost  # update cost
                prevNodes[str(neighbor)] = curr_node  # update prev

                # calc alternate path
                altpath = totalCosts[str(curr_node)] + self.graph.val_edges[curr_node][neighbor]
                # val_edges is a adj_matrix with values for the connecting edges

                if altpath < totalCosts[str(neighbor)]:  # check if new path is better
                    totalCosts[str(neighbor)] = altpath
                    prevNodes[str(neighbor)] = curr_node

                    minPQ.decrease_key(neighbor, altpath)

Что, на мой взгляд, должно решить вышеупомянутую проблему (оптимальный путь от начального узла до любого другого узла). Но это не так. Может ли кто-нибудь помочь мне убрать этот беспорядок, который я пытался отладить уже некоторое время. Заранее спасибо!

Предположение:

Фактически я понял, что в моих словарях хранятся ранее посещенные узлы ( prevNodes ) и тот, в котором я сохраняю соответствующую общую стоимость посещения узла ( totalCosts ) неравно длинные . И я не понимаю, почему.