АЛГОРИТМ ДЕЙКСТРЫ PYTHON

Алгоритм Дейкстры (Dijkstra's algorithm) - это алгоритм на графах, который находит кратчайший путь между двумя вершинами. Он часто используется в компьютерных сетях и маршрутизации. Описанный в 1959 году в работе Эдсгера Дейкстры, алгоритм Дейкстры может быть реализован на языке программирования Python с использованием классической структуры данных - кучей (heap).

Код на Python для реализации алгоритма Дейкстры может выглядеть следующим образом:

import heapqimport sysdef dijkstra(graph, start):    distances = {node: sys.maxsize for node in graph}     distances[start] = 0    heap = [(0, start)]    while heap:        (current_weight, current_node) = heapq.heappop(heap)        if current_weight > distances[current_node]:            continue        for neighbor, weight in graph[current_node].items():            distance = current_weight + weight            if distance < distances[neighbor]:                distances[neighbor] = distance                heapq.heappush(heap, (distance, neighbor))    return distances

В этом примере кода мы импортируем модуль heapq и sys. Модуль heapq содержит функцию heappush и heappop, которые позволяют работать с кучей. Модуль sys используется для получения максимального значения.

Далее мы создаем функцию dijkstra, которая принимает граф и вершину начала. Мы используем словарь для хранения расстояний до каждой вершины, а начальное расстояние устанавливаем в 0. Куча инициализируется с начальным весом 0 и вершиной начала.

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

Наконец, мы возвращаем наш словарь расстояний.