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

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

Основные принципы:

• Алгоритм работает в пошаговом режиме.
• На каждом шаге выбирается еще не обработанная вершина с минимальным текущим расстоянием от начальной.
• Расстояния до смежных вершин обновляются, если найден более короткий путь через текущую вершину.

Шаги алгоритма:

1. Инициализировать расстояния до всех вершин как бесконечность, кроме начальной вершины, расстояние до которой равно 0.
2. Создать набор вершин, которые еще не были обработаны.
3. Повторять, пока есть необработанные вершины: а. Выбрать необработанную вершину u с минимальным расстоянием. б. Пометить u как обработанную. в. Для каждой смежной вершины v вершины u: i. Если расстояние до v больше, чем расстояние до u плюс вес ребра u->v, обновить расстояние до v.

Пример реализации (псевдокод):

// Функция Дейкстры
function dijkstra(graph, start_node):
    distances = {} // Словарь для хранения кратчайших расстояний
    unvisited_nodes = set(graph.get_nodes()) // Множество необработанных вершин

    // Инициализация расстояний
    for node in graph.get_nodes():
        distances[node] = infinity
    distances[start_node] = 0

    while unvisited_nodes:
        // Найти необработанную вершину с минимальным расстоянием
        current_node = get_node_with_min_distance(unvisited_nodes, distances)

        if distances[current_node] == infinity:
            break // Несвязанные вершины

        unvisited_nodes.remove(current_node)

        // Обновить расстояния для смежных вершин
        for neighbor, weight in graph.get_neighbors(current_node):
            new_distance = distances[current_node] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance

    return distances

// Вспомогательная функция для поиска вершины с минимальным расстоянием
function get_node_with_min_distance(unvisited_nodes, distances):
    min_distance = infinity
    min_node = None
    for node in unvisited_nodes:
        if distances[node] < min_distance:
            min_distance = distances[node]
            min_node = node
    return min_node

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

• Используя списки и линейный поиск минимального расстояния: O(V^2), где V - количество вершин.
• Используя очередь с приоритетом (например, бинарную кучу): O((V + E) log V), где E - количество рёбер.

Применение:

• Поиск кратчайших маршрутов на картах (GPS-навигаторы).
• Маршрутизация в компьютерных сетях.
• Поиск кратчайших путей в графах зависимостей.