Статья Автор: Деникина Н.В., Деникин А.В.

Алгоритм Дейкстры с использованием модуля heapq

Реализация алгоритма Дейкстры для поиска кратчайшего пути в графе с использованием кучи с приоритетом (модуль heapq в Python)

import heapq

def dijkstra(graph, start):
    # Словарь для хранения кратчайших расстояний до каждой вершины
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0  # Расстояние до стартовой вершины равно 0

    # Куча с приоритетом для хранения вершин и их текущих расстояний
    priority_queue = [(0, start)]

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

        # Если текущее расстояние больше уже найденного, пропускаем
        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(priority_queue, (distance, neighbor))

    return distances

# Пример взвешенного графа
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# Вызов алгоритма Дейкстры
start_vertex = 'A'
shortest_distances = dijkstra(graph, start_vertex)

# Вывод результатов
print(f"Кратчайшие расстояния от вершины {start_vertex}:")
for vertex, distance in shortest_distances.items():
    print(f"До вершины {vertex}: {distance}")

Пояснение

Граф представлен в виде словаря, где ключи — это вершины, а значения — словари соседей с весами рёбер.
- Например, 'A': {'B': 1, 'C': 4} означает, что из вершины A есть ребро в B с весом 1 и в C с весом 4.
Куча с приоритетом (priority_queue) используется для хранения вершин и их текущих расстояний. Вершина с наименьшим расстоянием извлекается первой.
Алгоритм:
- Инициализируем расстояния до всех вершин как бесконечность (float('infinity')), кроме стартовой вершины (её расстояние равно 0).
- Добавляем стартовую вершину в кучу.
- Пока куча не пуста:
  - Извлекаем вершину с минимальным расстоянием.
  - Обновляем расстояния до её соседей, если найден более короткий путь.
  - Добавляем обновлённые расстояния в кучу.
Результат:
- Возвращается словарь distances, где для каждой вершины указано кратчайшее расстояние от стартовой вершины.

Сложность

Временная сложность: O((V + E) * log V), где V — количество вершин, E — количество рёбер.
Пространственная сложность: O(V) для хранения расстояний и O(V) для кучи.

Эта реализация эффективна для разреженных графов (где количество рёбер значительно меньше, чем V²).

Чтобы оставить комментарий нужна авторизация

Печать

Алгоритм Дейкстры с использованием модуля heapq

Пояснение

Сложность

Временная сложность: O((V + E) * log V), где V — количество вершин, E — количество рёбер.