Алгоритм Дейкстры: Введение
Алгоритм Дейкстры - это алгоритм для нахождения кратчайшего пути в графе с неотрицательными длинами рёбер. То есть, мы ищем путь между двумя вершинами, сумма весов рёбер которого минимальна. Алгоритм был предложен в 1959 году Эдсгером Дейкстрой и является одним из основных алгоритмов на графах.
Основные обозначения:
G = (V, E) - граф с множеством вершин V и множеством рёбер E; s - стартовая вершина, из которой мы хотим найти кратчайший путь; t - конечная вершина, до которой мы ищем кратчайший путь.
Идея алгоритма Дейкстры
Алгоритм состоит из двух основных этапов:
- Инициализация: каждому ребру графа присваивается вес 0, и всем вершинам, кроме стартовой, присваивается большое значение, например, INF. Это значение не должно быть меньше суммы весов всех рёбер графа. В результате кратчайший путь до стартовой вершины равен 0, а до всех остальных вершин - бесконечно большому числу.
- Постепенное улучшение: на каждом шаге мы выбираем вершину с наименьшим значением, и пытаемся улучшить значения всех смежных с ней вершин. Если это возможно, то мы уменьшаем значение смежной вершины на вес ребра, соединяющего эти две вершины. Этот процесс повторяется до тех пор, пока все вершины не получат свои окончательные значения.
Важным моментом в алгоритме является выбор “правильного” порядка обхода вершин. Для этого используется так называемая “система приоритетов” - каждой вершине присваивается значение, которое является оценкой расстояния от стартовой вершины до этой вершины. Изначально это значение равно бесконечности, и на каждом шаге выбирается вершина с наименьшим приоритетом. Когда мы улучшаем значение одной вершины, мы также улучшаем приоритеты всех смежных вершин, если это возможно.
Реализация алгоритма Дейкстры на Python
import sys
Функция для нахождения кратчайшего пути алгоритмом Дейкстры
def dijkstra(graph, start_vertex):
# Матрица смежности графа
adjacency_list = graph
# Создаем массив для хранения значений вершин
vertex_values = [float('inf')] * len(graph)
# Устанавливаем стартовую вершину в 0
vertex_values[start_vertex] = 0
Продолжи
Система приоритетов на основе массива значений вершин
priority_queue = [(vertex_values[v], v) for v in range(len(vertex_values))]
while priority_queue:
# Выбираем вершину с наименьшей оценкой
min_vertex = heapq.heappop(priority_queue)[1]
for v in adjacency_list[min_vertex]:
# Улучшаем оценку смежной вершины
if vertex_values[min_vertex] + adjacency_list[min_vertex][v] < vertex_values[v]:
vertex_values[v] = vertex_values[min_vertex] + adjacency_list[min_vertex][v]
heapq.heapreplace(priority_queue, (vertex_values[v], v))
return vertex_values
Пример использования функции
graph = {
‘A’: {‘B’: 4, ‘C’: 2},
‘B’: {‘A’: 4, ‘D’: 3, ‘E’: 5},
‘C’: {‘A’: 2, ‘F’: 1},
‘D’: {‘B’: 3},
‘E’: {},
‘F’: {‘C’: 1}
}
start_vertex = ‘A’
result = dijkstra(graph, start_vertex)
print(result)
Эта статья описывает алгоритм Дейкстры для нахождения кратчайшего пути между двумя вершинами в графе. Данный алгоритм является одним из наиболее популярных и важных алгоритмов на графах, и он широко используется в различных приложениях, таких как планирование маршрутов, оптимизация сетей и т.д.
► Ссылка на приложения для тренировки мозга:
Счет на скорость — Яндекс Игры
yandex.ru
Счет чисел в уме — Яндекс Игры
yandex.ru
►Ссылка на rutube: https://rutube.ru/channel/23484297/
►Ссылка на группу в ВК: https://vk.com/dragon_vl
►Донат на улучшения качества видео: