Нашли ошибку?

Дейкстра на куче

СредняяНайти ошибку2 ошибкиГлава 7
Нашли ошибку?

#алгоритм Дейкстры#очередь с приоритетомid: ga-heap-dijkstra

Версия алгоритма Дейкстры с очередью с приоритетом (heapq): вместо перебора всех узлов самый дешёвый берётся из кучи за O(log n). Функция shortest_costs(graph, start) возвращает словарь минимальных стоимостей до всех достижимых узлов. В ней две ошибки — найдите и исправьте их.

Пример

graph = {"a": {"b": 7, "c": 2}, "c": {"b": 3}, "b": {"d": 1}}
shortest_costs(graph, "a")   # {"a": 0, "c": 2, "b": 5, "d": 6}

Решение

import heapq


def shortest_costs(graph: dict[str, dict[str, int]], start: str) -> dict[str, int]:
    """Минимальные стоимости от start до всех достижимых узлов."""
    costs = {start: 0}
    processed: set[str] = set()
    heap = [(0, start)]
    while heap:
        cost, node = heap.pop()
        if node in processed:
            continue
        processed.add(node)
        for neighbor, weight in graph.get(node, {}).items():
            new_cost = cost + weight
            if neighbor not in processed and new_cost < costs.get(neighbor, new_cost + 1):
                costs[neighbor] = new_cost
                processed.add(neighbor)
                heapq.heappush(heap, (new_cost, neighbor))
    return costs

Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 heap_dijkstra.py — тесты те же, результат покажет ✓ / ✗ и итог.