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

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

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

Пример кода на Python для реализации алгоритма Дейкстры:

import heapq
def dijkstra(graph, start):
    distances = {vertex: float('infinity') 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': 2, 'C': 1},
    'B': {'A': 2, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 3},
    'D': {'B': 1, 'C': 4, 'E': 1},
    'E': {'C': 3, 'D': 1}
}
print(dijkstra(graph, 'A'))  # Выводит {'A': 0, 'B': 2, 'C': 1, 'D': 3, 'E': 4}

В этом примере мы создаем функцию `dijkstra`, которая принимает на вход граф и начальную вершину, и возвращает словарь с расстоянием до каждой вершины. Внутри функции мы инициализируем словарь расстояний для каждой вершины как бесконечность, за исключением начальной вершины, которая имеет расстояние 0. Затем мы инициализируем очередь с приоритетом (heapq) и добавляем начальную вершину с расстоянием 0.

На каждой итерации цикла мы извлекаем вершину из очереди с наименьшим расстоянием и проверяем, посетили ли мы уже эту вершину. Затем мы перебираем все соседние вершины и обновляем расстояние через них, если новое расстояние меньше сохраненного. Наконец, мы добавляем обновленные вершины в очередь с приоритетом.

Как результат, мы получаем словарь расстояний до каждой вершины в графе. В данном случае, это словарь {'A': 0, 'B': 2, 'C': 1, 'D': 3, 'E': 4}, что означает, что кратчайший путь от вершины A до каждой другой вершины в графе составляет соответствующее расстояние.