Крипто Devs | Gnezdo Hub

Теперь разберём реализацию алгоритма на языке Python с использованием модуля heapq, который предоставляет приоритетную очередь. Приоритетная очередь отличается от обычной тем, что всегда возвращает элемент с наименьшим ключом (в нашем случае — расстоянием). Это как раз соответствует жадному выбору ближайшей вершины.

import heapq  # Модуль для приоритетной очереди (мин-куча)

def dijkstra(graph, start):
    # 1. Инициализация: все расстояния = бесконечность
    distances = {node: float("infinity") for node in graph}
    distances[start] = 0  # До стартовой вершины — 0

    # 2. Приоритетная очередь: (расстояние, вершина)
    # heapq всегда отдаёт элемент с МИНИМАЛЬНЫМ расстоянием первым
    priority_queue = [(0, start)]

    while priority_queue:
        # 3. Извлекаем вершину с наименьшим расстоянием
        current_distance, current_node = heapq.heappop(priority_queue)

        # 4. Устаревшая запись? Пропускаем
        # (в очереди могут быть старые версии с большим расстоянием)
        if current_distance > distances[current_node]:
            continue

        # 5. Обходим соседей
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # 6. Нашли более короткий путь? Обновляем!
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

Поясним некоторые детали реализации. Строка if current_distance > distances[current_node]: continue необходима для отбрасывания устаревших записей в очереди. Когда мы обновляем расстояние до вершины (например, C с 4 на 3), старая запись (4, C) остаётся в куче. Когда она позже извлекается, мы проверяем, что её расстояние больше текущего известного, и просто пропускаем её. Это экономит время и корректирует работу алгоритма.

Важно понимать, почему используется именно приоритетная очередь. Если бы мы каждый раз искали минимум простым перебором, сложность стала бы квадратичной. Благодаря этому мы получаем эффективность: каждая операция извлечения минимума и вставки стоит O(log V), где V — число вершин.

Сложность алгоритма Дейкстры с приоритетной очередью составляет O((V + E) log V), где V — количество вершин, E — количество рёбер. Для большинства реальных задач, таких как прокладка маршрутов на карте или в сетях, это приемлемо быстро.

Однако у алгоритма Дейкстры есть важное ограничение: он работает только с неотрицательными весами рёбер. Почему это так? Дело в том, что алгоритм основан на гарантии: когда вершина извлекается из очереди с минимальным расстоянием, это расстояние уже окончательное и не может быть улучшено позже. Если бы существовали отрицательные рёбра, то путь через другую вершину, ещё не обработанную, мог бы дать меньшее расстояние, даже если текущая вершина уже «закрыта». Рассмотрим простой пример:

A ──2── B ──(−5)── C
A ─────────4───── C

Дейкстра из A сначала установит расстояния: B=2, C=4. Затем извлечёт B (расстояние 2) и пометит его как финальное. При обработке B он обновит C: 2 + (−5) = −3, и это станет новым расстоянием до C. Однако теперь уже поздно пересматривать пути через другие вершины, потому что B уже обработан. В этом конкретном случае мы всё же получим правильный ответ, но в более сложных графах с отрицательными весами могут возникнуть ситуации, когда оптимальный путь требует пересмотра уже обработанных вершин, что невозможно в рамках алгоритма Дейкстры. Более того, отрицательные веса могут создавать циклы с отрицательной суммой, которые делают понятие кратчайшего пути вообще неопределённым (можно бесконечно уменьшать стоимость, обходя цикл).

Если в графе присутствуют отрицательные веса, следует использовать алгоритм Беллмана–Форда. Он не полагается на жадный выбор и не делает предположений о финальности расстояний. Вместо этого алгоритм выполняет V−1 проходов по всем рёбрам, каждый раз пытаясь улучшить расстояния. Вот его простая реализация:

📟 Прилетело из @solidityset

20 views08:53