Поиск оптимальных путей в графе
(Алгоритм Дейкстры)

Теория и методология алгоритма Дейкстры

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

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

Принцип работы

Алгоритм поддерживает множество вершин, для которых кратчайшее расстояние уже известно, и на каждом шаге «расширяет» это множество:

1. Расстояние до стартовой вершины полагается равным 0, до всех остальных — бесконечности.
2. Из ещё не посещённых вершин выбирается та, у которой текущая оценка расстояния минимальна.
3. Для каждого соседа выбранной вершины выполняется релаксация: если путь через текущую вершину короче уже известного, оценка обновляется.
4. Вершина помечается как посещённая, шаги 2–3 повторяются, пока не будут обработаны все вершины.

Реализация с очередью с приоритетом

Наивная реализация перебирает все непосещённые вершины на каждом шаге за O(n), что даёт общую сложность O(n²). Если вместо этого использовать бинарную кучу (в Python — модуль heapq) как очередь с приоритетом, сложность снижается до O(m·log n), где m — число рёбер, n — число вершин.

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

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances

graph = {
         'A' : {'B' : 4, 'C' : 2},
         'B' : {'A' : 4, 'C' : 1, 'D' : 5},
         'C' : {'A' : 2, 'B' : 1, 'D' : 8, 'E' : 10},
         'D' : {'B' : 5, 'C' : 8, 'E' : 2},
         'E' : {'C' : 10, 'D' : 2}
}
print(dijkstra(graph, 'A'))

Сложность алгоритма

• O(n²) — наивная реализация с линейным поиском минимума на каждой итерации.
• O(m·log n) — реализация на бинарной куче (heapq), эффективна для разреженных графов.
• O(m + n·log n) — реализация на куче Фибоначчи (теоретический оптимум).

Ограничения

• Алгоритм не работает корректно с рёбрами отрицательного веса — в этом случае используют алгоритм Беллмана — Форда.
• Является жадным: раз вершина помечена как посещённая, её расстояние больше не пересматривается.
• Для поиска кратчайшего пути между всеми парами вершин эффективнее алгоритм Флойда — Уоршелла.

Разбор примера графа

Таблица 1. Матрица смежности графа из примера на Python (вес ребра между вершинами; «—» — ребро отсутствует)

Таблица 2. Список смежности (тот же граф в виде, в котором он задан в коде на Python)

Таблица 3. Итоговые кратчайшие расстояния от вершины A (результат работы dijkstra(graph, 'A'))

{'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}

Исполняющий код Python алгоритм Дейкстра

Пример реализации на python