Алгоритм Дейкстры на пальцах

Алгоритм Дейкстры находит кратчайшее расстояние от одной вершины графа до всех остальных, если все веса рёбер неотрицательные. Классический пример применения — построение маршрутов на карте.

Идея

Держим для каждой вершины текущую лучшую известную оценку расстояния от старта. На каждом шаге берём ещё не обработанную вершину с наименьшей оценкой, «фиксируем» её и пробуем через неё улучшить оценки соседей. Так постепенно расстояния становятся окончательными.

Реализация на Python

Для эффективного выбора вершины с минимальной оценкой используем кучу (heapq) — она даёт следующий минимум за O(log n).

import heapq

def dijkstra(graph: dict[str, list[tuple[str, int]]], start: str) -> dict[str, float]:
    distances = {node: float("inf") for node in graph}
    distances[start] = 0

    queue = [(0, start)]
    visited = set()

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

Пример графа и вызова:

graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("A", 4), ("C", 2), ("D", 5)],
    "C": [("A", 1), ("B", 2), ("D", 8)],
    "D": [("B", 5), ("C", 8)],
}

print(dijkstra(graph, "A"))
# {'A': 0, 'B': 3, 'C': 1, 'D': 8}

Почему B получает расстояние 3, а не 4

Прямое ребро A → B стоит 4, но есть путь A → C → B ценой 1 + 2 = 3, который дешевле. Алгоритм находит его, потому что после обработки вершины C он пересчитывает оценку для B и видит более короткий путь.

Сложность

• С кучей: O((V + E) log V), где V — число вершин, E — число рёбер.
• Без кучи (наивный перебор минимума): O(V²) — выгоднее только на очень плотных графах.

Типичные ошибки

• Забыть пропускать уже посещённые вершины — тогда одна и та же вершина обрабатывается много раз.
• Использовать алгоритм на графе с отрицательными весами — результат будет неверным без явной ошибки.
• Хранить в очереди только вершину без расстояния — тогда куча не сможет упорядочить элементы правильно.