Алгоритмы поиска путей на пальцах. Часть 2: Алгоритм Дейкстры

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

Теперь вы, как специалист на посту разработчика 2GIS изучили местность более подробно и поняли, что BFS не подходит для решения вашей задачи, так как дороги имеют разную протяженность и маршрут от A до B не может исчисляться в условной единице.

В первой части мы рассмотрели:

• Что такое графы, как их читать и составлять

• Как работает алгоритм поиска в ширину (BFS)

• Что такое двусторонняя очередь (модуль deque)

Во этой части рассмотрим:

• Как работает алгоритм Дейкстры

• Что такое кучи и очередь с приоритетом (модуль heapq)

Читать первую часть

---

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

Подписаться

---

Взвешенный граф

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

Основные характеристики взвешенных графов:

1. Веса на ребрах: Каждому ребру e приписано значение w(e), где w(e) — вес этого ребра.

2. Типы взвешенных графов:

   • Ориентированные (направленные) графы: веса назначаются направленным ребрам, и связь от вершины A к вершине B может отличаться от связи от B к A.

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

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

Пример взвешенного графа:

Если у нас есть вершины A, B, и C и следующие связи:

• Ребро A → B с весом 5,

• Ребро A → C с весом 2,

• Ребро B → C с весом 1.

Это значит, что перемещение между A и B связано с затратой 5 единиц, между A и C — с затратой 2 единицы, и так далее.

Учитывая новые данные, рабочий граф выглядит так:

Напомню, что в прошлом разделе кратчайший путь от Home до Theater был такой:

[Home, Park, Cafe, Theater]

Мы пришли к такому выводу, потому что алгоритм поиска в ширину возвращает кратчайший путь не учитывая веса рёбер.

Теперь это не соответствует действительности. Самый короткий путь от Home до Theater на взвешенном графе будет такой:

[Home, Park, Museum, Shop, Theater]

Объяснение этому простое: ребра в новом графе обладают весами, имитируя протяженность дороги. Допустим что вес ребра — это число километров. Тогда от Home до Park лежит дорога длиной 2 километра. Теперь мы можем посчитать длину каждого пути в километрах от Home до Theater. Длина маршрута определенного BFS ([Home, Park, Cafe, Theater]) составляет 13 километров. Тогда как длина маршрута [Home, Park, Museum, Shop, Theater] составляет 12 километров. Теперь мы видим разницу. Не смотря на то, что второй маршрут содержит больше узлов, его общая протяженность меньше протяженности первого маршрута.

Так будет выглядеть граф с весами в виде словаря:

city_map = {       'Home': {'Park': 2, 'School': 5, 'Mail': 10},       'Park': {'Home': 2, 'Museum': 4, 'Cafe': 3},       'School': {'Home': 5, 'Library': 6, 'Mail': 2},       'Mail': {'Home': 10, 'School': 2, 'Hospital': 3},       'Library': {'School': 6, 'Hospital': 1},       'Hospital': {'Library': 1, 'Mail': 3, 'Office': 4},       'Cafe': {'Park': 3, 'Theater': 8, 'Office': 7},       'Museum': {'Park': 4, 'Shop': 5},       'Shop': {'Museum': 5, 'Theater': 1},       'Theater': {'Shop': 1, 'Cafe': 8},       'Office': {'Cafe': 7, 'Hospital': 4}   }

Для поиска в ширину нам было достаточно списка соседей в виде значения для каждого узла. Теперь каждое значение ключа — это словарь, где значением каждого соседа является вес ребра, соединяющего узел-сосед и основной узел.

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

Реализация алгоритма

Для начала посмотрим как происходит поиск кратчайшего пути непосредственно на взвешенном графе:

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

Основные принципы алгоритма

1. Инициализация: Начальная вершина (источник) получает метку расстояния, равную нулю, все остальные вершины получают метку бесконечности (или максимального возможного значения), что означает, что путь до них пока не найден.

2. Посещение вершин: На каждом шаге выбирается непосещённая вершина с минимальной меткой расстояния, которая рассматривается как текущая.

3. Обновление расстояний: Для каждой смежной вершины текущей вершины проверяется, можно ли уменьшить метку расстояния, пройдя через текущую вершину. Если можно, то метка обновляется.

4. Завершение: Процесс повторяется до тех пор, пока не будут посещены все вершины, или пока метка ближайшей вершины не будет равна бесконечности (что означает, что оставшиеся вершины недостижимы).

Посмотрим на решение, а затем всё подробно разберем.

import heapq         def dijkstra_shortest_path(city_map, start, goal):       queue = [(0, start, [])]       distances = {node: float('inf') for node in city_map}       distances[start] = 0       visited = set()          while queue:           current_distance, node, path = heapq.heappop(queue)              if node in visited:               continue              visited.add(node)              path = path + [node]              if node == goal:               return path, current_distance             for neighbor, distance in city_map[node].items():               if neighbor not in visited:                   old_cost = distances[neighbor]                   new_cost = current_distance + distance                                      if new_cost < old_cost:                       distances[neighbor] = new_cost                       heapq.heappush(queue, (new_cost, neighbor, path))          return float('inf'), None       city_map = {...}      start = 'Home'   goal = 'Theater'   distance, shortest_path = dijkstra_shortest_path(city_map, start, goal)   print("Кратчайший путь от Home до Theater:", shortest_path)   print("Общая длина пути:", distance)  # >>> Кратчайший путь от Home до Theater: ['Home', 'Park', 'Museum', 'Shop', 'Theater'] # >>> Общая длина пути: 12

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

Кучи и очереди с приоритетом

Для реализации мы будем использовать модуль — heapq. Для глубокого понимания можно обратиться к документации или прочитать какую-нибудь статью. Мне понравилась эта. Я же дам информацию, необходимую для понимания алгоритма.

Очередь с приоритетом: heapq — это очередь, которая каждый раз позволяет извлекать узел с наименьшим текущим весом пути. Это важно, поскольку алгоритм Дейкстры всегда продолжает с узла, для которого найден кратчайший путь на текущем этапе.

Минимальная куча: В python куча (heap) — это структура данных, где наименьший элемент находится на вершине. Использование heapq позволяет автоматически поддерживать порядок элементов.

Нам понадобятся 2 метода: heappop и heappush . Посмотрим наглядно как они работают:

import heapq  queue = [3, 6, 1, 8, 9, 5]  # Удаление элементов из кучи heapq.heappop(queue) print(queue)  # Добавление элементов в кучу   heapq.heappush(queue, 0)   print(queue)   heapq.heappush(queue, 20)   print(queue)  # >>> [1, 6, 5, 8, 9] # >>> [0, 6, 1, 8, 9, 5] # >>> [0, 6, 1, 8, 9, 5, 20]

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

Если вы применяете heappop() к еще необработанному списку, метод вернет первый элемент, а не минимальный, так как список до этого еще не был сортирован.

Для нас это не важно, так как впервые мы обращаемся к списку, когда там всего 1 элемент.

Инициализация функции

Импортируем heapq и создаем функцию, которая в аргументах принимает граф, стартовый и конечный узлы.

def dijkstra_shortest_path(city_map, start, goal):        queue = [(0, start, [])]        distances = {node: float('inf') for node in city_map}       distances[start] = 0        visited = set()

Перед тем, как перейти к логике, нам нужно объявить 3 набора данных:

1. Список (очередь) кортежей. Структура кортежей следующая: длина пути (int) -> текущий узел (str) -> пройденный путь до текущего узла (list(str)).

• 0 — начальное расстояние до start.

• start — начальная вершина.

• [] — пустой список для хранения пути к start.

queue = [(0, start, [])] 

2. Словарь distances, в котором для каждого узла графа расстояние инициализируется как «бесконечность» (float('inf')). Это означает, что пока расстояние до каждого узла неизвестно. Для start сразу устанавливаем расстояние 0, поскольку оно является начальной точкой.

distances = {node: float('inf') for node in city_map}   distances[start] = 0  

3. Множество visited, которое будет хранить посещенные узлы, чтобы не обрабатывать их повторно.

visited = set()

Цикл while

Запускаем цикл while, который работает, пока очередь queue не пуста. Мы не знаем необходимое количество итераций, поэтому не можем использовать цикл for.

while queue:  

1. Извлекаем из queue элемент с минимальным расстоянием (так как используем heapq, это будет первый элемент). Так как узел — это кортеж, распечатываем его в переменные:

• current_distance — текущее минимальное расстояние до node.

• node — текущий узел.

• path — текущий путь, ведущий к этому узлу.

while queue:       current_distance, node, path = heapq.heappop(queue) 

2. Если текущий узел node уже был посещен (есть в visited), пропускаем его и переходим к следующему элементу.

while queue:   current_distance, node, path = heapq.heappop(queue)    if node in visited:   continue  

3. Добавляем node в visited, чтобы избежать его повторной обработки.

while queue:       ... visited.add(node) 

4. Добавляем текущий узел node к пути path.

while queue:       ... visited.add(node)     path += [node]  

5. Если текущий узел node является целевым goal, то возвращаем найденный path и current_distance, так как мы нашли кратчайший путь.

while queue:       ... if node == goal:   return path, current_distance  

Собираем части в цельный код:

while queue:   current_distance, node, path = heapq.heappop(queue)    if node in visited:   continue    visited.add(node)    path += [node]    if node == goal:   return path, current_distance  

Цикл for. Обработка соседей.

1. В цикле for мы будем итерироваться по словарю с соседями текущего узлу. Нам понадобятся ключ neighbor и вес distance из city_map[node].

for neighbor, distance in city_map[node].items():

2. Если соседний узел neighbor еще не был посещен, продолжаем его обработку. Иначе пропускаем итерацию.

for neighbor, distance in city_map[node].items():       if neighbor not in visited: 

3. Создаем переменную old_cost — текущее известное расстояние до neighbor из словаря distances. Создаем переменную new_cost — расстояние до neighbor через node, полученное сложением distance с current_distance.

for neighbor, distance in city_map[node].items():       if neighbor not in visited:           old_cost = distances[neighbor]         new_cost = current_distance + distance

4. Если new_cost меньше, чем old_cost, это означает, что найден новый кратчайший путь до neighbor.

• Обновляем distances[neighbor] значением new_cost.

• Добавляем (new_cost, neighbor, path) в queue для дальнейшей обработки, используя heapq.heappush для сохранения приоритета по минимальной дистанции.

for neighbor, distance in city_map[node].items():       if neighbor not in visited:           ...         if new_cost < old_cost:               distances[neighbor] = new_cost             heapq.heappush(queue, (new_cost, neighbor, path))

В случае когда new_cost оказывается больше чем old_cost, программа перейдет к следующей итерации.

Если очередь опустела и мы не нашли путь до goal, возвращаем (float('inf'), None), что означает, что пути до целевого узла не существует.

Теперь можно вернуться к готовому коду и изучить структуру с обновленными знаниями.

Итоги

Конечно тема графов и алгоритмов для поиска пути более объемная, чем мои две статьи Но я питаю надежду, что моё пояснение позволит кому то заложить основу и увлечься этой темой. Я смог разобраться во всём что написал, верю и у вас получится.

---

Good coding!

Телеграм канал о разработке на python — Don Python

Первая часть — Алгоритмы поиска путей на пальцах. Часть 1: Поиск в ширину

Ресурсы

1. Редактор графов

2. Редактор gif

3. Пособие по алгоритмам