Сейчас я работаю над реализацией метода Дейкстры для задачи обхода графа, но не могу разобраться. Я получаю неправильные результаты для кратчайшего пути, несмотря на то, что следую этапам алгоритма и использую приоритетную очередь для выбора узла.
Я дважды проверил представление своего графа, чтобы убедиться, что веса ребер не являются отрицательными. Я также подтвердил, что моя реализация приоритетной очереди правильно поддерживает узлы минимального расстояния. Когда я выполняю алгоритм в разных тестовых сценариях, пути вывода не соответствуют ожидаемым результатам.
Код:
for neighbor in graph[node]:
new_distance = distances[node] + edge_weight(node, neighbor)
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
priority_queue.push(neighbor, new_distance)
Я использовал метод с ручкой и бумагой, отлаживая свой код и сравнивая его с псевдокодом и инструкциями, которые я узнал из чтения блога scaler. Явных недостатков или ошибок не вижу. Я также пытался запустить алгоритм в небольших сетях, чтобы сузить круг проблем, но все равно получаю неточные результаты.
Социальные закладки