Алгоритм Дейкстры (Dijkstra’s Algorithm) — это классический алгоритм для нахождения кратчайших путей от одной вершины-источника до всех остальных вершин во взвешенном графе с Неотрицательными весами ребер. Он является "жадным" алгоритмом и широко используется в сетевой маршрутизации и других задачах, связанных с графами.
Основная идея алгоритма Дейкстры:
Инициализация: Устанавливаем расстояние до начальной вершины равным 0, а до всех остальных вершин — бесконечности. Создаем набор посещенных вершин (изначально пустой). Повторение:
Выбираем непосещенную вершину с наименьшим текущим расстоянием от источника. Помечаем эту вершину как посещенную. Для каждой соседней вершины:
Вычисляем новое расстояние до этой соседней вершины через текущую вершину (текущее_расстояние_до_текущей_вершины + вес_ребра). Если это новое расстояние меньше текущего известного расстояния до соседней вершины, обновляем его.
Завершение: Алгоритм завершается, когда все вершины посещены или когда вершина, до которой мы ищем путь, выбрана (если ищется путь до конкретной вершины).
Представление графа
Для реализации алгоритма Дейкстры обычно используется представление графа в виде Списка смежности (adjacency list). Это словарь, где ключи — вершины, а значения — другие словари, представляющие смежные вершины и веса ребер до них.
Пример:
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}
}
Использование очереди с приоритетом (Priority Queue)
Для эффективного выбора следующей непосещенной вершины с наименьшим расстоянием алгоритм Дейкстры использует Очередь с приоритетом (min-priority queue). В Python это легко реализовать с помощью модуля heapq, который предоставляет реализацию кучи (heap).
Элементы в очереди с приоритетом будут кортежами (расстояние, вершина). heapq автоматически сортирует кортежи по первому элементу, что позволяет всегда извлекать вершину с наименьшим расстоянием.
Реализация алгоритма Дейкстры на Python
Python
Import heapq
Def dijkstra(graph, start_node):
"""
Реализует алгоритм Дейкстры для нахождения кратчайших путей
от стартовой вершины до всех остальных во взвешенном графе
с неотрицательными весами ребер.
:param graph: Словарь, представляющий граф.
Пример: {‘A’: {‘B’: 1, ‘C’: 4}, ‘B’: {‘A’: 1, ‘C’: 2, ‘D’: 5}}
:param start_node: Стартовая вершина.
:return: Кортеж (distances, previous_nodes)
distances: Словарь, содержащий кратчайшие расстояния от start_node
до всех других вершин.
previous_nodes: Словарь, содержащий предыдущую вершину на кратчайшем пути
до каждой вершины (для восстановления пути).
"""
# Инициализация расстояний: бесконечность для всех вершин, 0 для стартовой
distances = {node: float(‘infinity’) for node in graph}
distances[start_node] = 0
# Словарь для восстановления кратчайшего пути
previous_nodes = {node: None for node in graph}
# Очередь с приоритетом (min-heap)
# Содержит кортежи (расстояние, вершина)
priority_queue = [(0, start_node)]
while priority_queue:
# Извлекаем вершину с наименьшим расстоянием из очереди
current_distance, current_node = heapq. heappop(priority_queue)
# Если мы уже нашли более короткий путь до этой вершины, пропускаем
# (это случается, потому что мы можем добавить одну и ту же вершину
# в очередь несколько раз с разными расстояниями)
if current_distance > distances[current_node]:
continue
# Перебираем всех соседей текущей вершины
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# Если найден более короткий путь до соседа
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_nodes[neighbor] = current_node # Обновляем предшественника
heapq. heappush(priority_queue, (distance, neighbor)) # Добавляем соседа в очередь с новым расстоянием
return distances, previous_nodes
Def reconstruct_path(previous_nodes, start_node, end_node):
"""
Восстанавливает кратчайший путь от стартовой до конечной вершины.
:param previous_nodes: Словарь предшествующих вершин, возвращаемый dijkstra().
:param start_node: Стартовая вершина.
:param end_node: Конечная вершина.
:return: Список вершин, представляющих кратчайший путь, или None, если путь не найден.
"""
path = []
current = end_node
while current is not None:
path. append(current)
if current == start_node:
break
current = previous_nodes[current]
if path and path[-1] == start_node:
return path[::-1] # Разворачиваем путь, чтобы он шел от start_node к end_node
else:
return None # Путь не найден (end_node недостижима от start_node)
# — Пример использования —
If __name__ == "__main__":
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, ‘E’: 3},
‘E’: {‘D’: 3, ‘F’: 2},
‘F’: {‘E’: 2}
}
start_node = ‘A’
distances, previous_nodes = dijkstra(graph, start_node)
print(f"Кратчайшие расстояния от {start_node}:")
for node, dist in distances. items():
print(f" До {node}: {dist}")
print("\nВосстановление путей:")
# Путь от A до E
path_A_to_E = reconstruct_path(previous_nodes, ‘A’, ‘E’)
print(f"Путь от A до E: {path_A_to_E} (Длина: {distances. get(‘E’, ‘Infinity’)})")
# Ожидаемый вывод: Путь от A до E: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’] (Длина: 7)
# (A -> B (1) -> C (2) -> D (1) -> E (3) = 1+2+1+3 = 7)
# Путь от A до F
path_A_to_F = reconstruct_path(previous_nodes, ‘A’, ‘F’)
print(f"Путь от A до F: {path_A_to_F} (Длина: {distances. get(‘F’, ‘Infinity’)})")
# Ожидаемый вывод: Путь от A до F: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’] (Длина: 9)
# Путь от A до A (сам до себя)
path_A_to_A = reconstruct_path(previous_nodes, ‘A’, ‘A’)
print(f"Путь от A до A: {path_A_to_A} (Длина: {distances. get(‘A’, ‘Infinity’)})")
# Путь до несуществующей вершины
path_A_to_Z = reconstruct_path(previous_nodes, ‘A’, ‘Z’)
print(f"Путь от A до Z: {path_A_to_Z} (Длина: {distances. get(‘Z’, ‘Infinity’)})")
# Пример для несвязанного графа (вершина ‘X’ не связана с ‘A’)
graph_disconnected = {
‘A’: {‘B’: 1},
‘B’: {‘A’: 1},
‘X’: {‘Y’: 1},
‘Y’: {‘X’: 1}
}
distances_dis, previous_nodes_dis = dijkstra(graph_disconnected, ‘A’)
print(f"\nРасстояния в несвязанном графе от ‘A’: {distances_dis}")
path_A_to_X = reconstruct_path(previous_nodes_dis, ‘A’, ‘X’)
print(f"Путь от A до X (несвязанный): {path_A_to_X}") # Вывод: None
Сложность алгоритма
Временная сложность:
При использовании массива для хранения расстояний и линейного поиска минимума: O(V2), где V — количество вершин. При использовании Очереди с приоритетом (кучи): O((V+E)logV), где E — количество ребер. Это гораздо эффективнее для разреженных графов (где E значительно меньше, чем V2).
Пространственная сложность: O(V+E) для хранения графа и O(V) для расстояний, предшественников и очереди с приоритетом.
Важные замечания:
Неотрицательные веса: Алгоритм Дейкстры Работает только с графами, у которых все веса ребер неотрицательны. Если в графе есть отрицательные веса, вам следует использовать алгоритм Беллмана-Форда (Bellman-Ford) или SPFA. Очередь с приоритетом: Использование heapq (минимальной кучи) является ключевым для эффективности алгоритма Дейкстры. Без неё он был бы значительно медленнее. Восстановление пути: Для восстановления пути нужно хранить, из какой вершины мы пришли к текущей вершине по кратчайшему пути. Float(‘infinity’): Используется для инициализации расстояний до непосещенных вершин.