Алгоритм Дейкстры на языке Python

Алгоритм Дейкстры

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

Алгоритм Дейкстры отличается своей эффективностью и применяется во многих областях, таких как сетевое планирование, транспортные системы, географическая информационная система (ГИС) и многое другое. Его основная идея заключается в том, чтобы построить дерево кратчайших путей от одной вершины к каждой другой вершине в графе.

Пример использования алгоритма Дейкстры на языке Python

Предположим, у нас есть взвешенный ориентированный граф и мы хотим найти кратчайший путь от стартовой вершины до каждой другой вершины.

import heapq

def dijkstra(graph, start):
    distances = {vertex: float("inf") for vertex in graph}  # инициализируем все расстояния как бесконечность
    distances[start] = 0  # расстояние от стартовой вершины до себя равно 0
    queue = [(0, start)]  # используем очередь с приоритетами для хранения вершин

    while queue:
        current_distance, current_vertex = heapq.heappop(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(queue, (distance, neighbor))  # добавляем соседнюю вершину в очередь

    return distances

# Пример использования алгоритма Дейкстры на графе:
graph = {
    'A': {'B': 5, 'C': 2},
    'B': {'D': 4, 'E': 3},
    'C': {'B': 1, 'E': 6},
    'D': {'F': 2},
    'E': {'F': 1, 'G': 3},
    'F': {'G': 2},
    'G': {}
}

start_vertex = 'A'
shortest_distances = dijkstra(graph, start_vertex)

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

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

После выполнения алгоритма мы получаем словарь с кратчайшими расстояниями от стартовой вершины до всех других вершин в графе. В приведенном выше коде мы применяем алгоритм Дейкстры к графу с вершинами A, B, C, D, E, F, G и ребрами с указанными весами. Затем мы выводим кратчайшие расстояния от стартовой вершины 'A' до каждой другой вершины.

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