Как работает алгоритм Дейкстры?

Идея. Храним текущие оценки расстояний dist: у старта 0, у остальных бесконечность. Повторяем:

1. достать из очереди с приоритетом вершину v с наименьшим dist;
2. для каждого ребра v → u с весом w: если dist[v] + w < dist[u], обновить dist[u] и положить u в очередь (это называется ослаблением ребра);
3. запоминать родителя, чтобы восстановить путь.

Почему это верно. Все веса неотрицательны, поэтому вершина, у которой сейчас наименьшая оценка, не может получить ещё меньшую через другие вершины — любой обходной путь только длиннее. Значит, в момент извлечения её расстояние окончательное. Это «жадный» шаг.

Отрицательные веса ломают рассуждение: обходной путь через отрицательное ребро может оказаться короче уже «окончательного». Для них используют алгоритм Беллмана — Форда (O(V·E)), он же находит отрицательные циклы.

Сложность с двоичной кучей — O((V + E) log V). Для невзвешенного графа Дейкстра вырождается в BFS. Если нужен путь до одной конкретной цели, можно остановиться, когда цель извлечена из очереди, а ещё лучше — использовать A* с эвристикой.

Применения: маршрутизация в сетях (OSPF), навигация, стоимость перемещения в играх.

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, v = heapq.heappop(heap)
        if d > dist.get(v, float("inf")):
            continue                      # устаревшая запись в куче
        for u, w in graph[v]:
            nd = d + w
            if nd < dist.get(u, float("inf")):
                dist[u] = nd
                heapq.heappush(heap, (nd, u))
    return dist