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

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

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

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

Структуры данных:

• Часто используются приоритетная очередь (например, на основе кучи) для эффективного выбора вершины с минимальным расстоянием.
• Массив или словарь для хранения текущих кратчайших расстояний.

Ограничения:

• Работает только с неотрицательными весами ребер.

# Пример реализации на Python с использованием heapq для приоритетной очереди
import heapq

def dijkstra(graph, start_node):
    distances = {node: float('inf') for node in graph} # Инициализация расстояний
    distances[start_node] = 0 # Расстояние до начальной вершины 0
    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 # Обновляем расстояние
                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_node = 'A'
shortest_paths = dijkstra(graph, start_node)
# print(shortest_paths) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}