В прошлой части мы разбирали алгоритм поиска в ширину, который находил самый короткий путь между узлами, основываясь на количестве пройденных рёбер.
Теперь вы, как специалист на посту разработчика 2GIS изучили местность более подробно и поняли, что BFS не подходит для решения вашей задачи, так как дороги имеют разную протяженность и маршрут от A до B не может исчисляться в условной единице.
В первой части мы рассмотрели:
Что такое графы, как их читать и составлять
Как работает алгоритм поиска в ширину (BFS)
Что такое двусторонняя очередь (модуль
deque
)
Во этой части рассмотрим:
Как работает алгоритм Дейкстры
Что такое кучи и очередь с приоритетом (модуль
heapq
)
Прежде чем мы продолжим, хочу пригласить в мой телеграмм канал Don Python, где я делюсь интересными особенностями языка, не очевидными фишками и решаю разные задачи.
Взвешенный граф
Взвешенный граф — это граф, в котором каждому ребру присвоено числовое значение, называемое весом. Веса могут отражать различные характеристики связей между вершинами, например, расстояние, стоимость, время или силу связи.
Основные характеристики взвешенных графов:
Веса на ребрах: Каждому ребру e приписано значение w(e), где w(e) — вес этого ребра.
-
Типы взвешенных графов:
Ориентированные (направленные) графы: веса назначаются направленным ребрам, и связь от вершины A к вершине B может отличаться от связи от B к A.
Неориентированные графы: веса назначаются без направления, то есть вес между двумя вершинами одинаков в обе стороны.
Применение весов: Взвешенные графы часто используются для нахождения оптимальных путей, минимальных расстояний и затрат. Например, в задаче о кратчайшем пути на графе веса могут представлять расстояния между городами.
Пример взвешенного графа:
Если у нас есть вершины 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 не сможет обработать это граф, поэтому вместо него будем использовать алгоритм Дейкстры — он как раз предназначен для поиска кратчайшего пути в графах с весами.
Реализация алгоритма
Для начала посмотрим как происходит поиск кратчайшего пути непосредственно на взвешенном графе:
Алгоритм Дейкстры последовательно выбирает узлы с минимальным текущим расстоянием от начального узла и обновляет расстояния для всех смежных узлов, если найдёт более короткий путь. Для каждого узла сохраняется минимальное расстояние от начального узла, которое является суммой весов рёбер, составляющих кратчайший путь к этому узлу.
Основные принципы алгоритма
Инициализация: Начальная вершина (источник) получает метку расстояния, равную нулю, все остальные вершины получают метку бесконечности (или максимального возможного значения), что означает, что путь до них пока не найден.
Посещение вершин: На каждом шаге выбирается непосещённая вершина с минимальной меткой расстояния, которая рассматривается как текущая.
Обновление расстояний: Для каждой смежной вершины текущей вершины проверяется, можно ли уменьшить метку расстояния, пройдя через текущую вершину. Если можно, то метка обновляется.
Завершение: Процесс повторяется до тех пор, пока не будут посещены все вершины, или пока метка ближайшей вершины не будет равна бесконечности (что означает, что оставшиеся вершины недостижимы).
Посмотрим на решение, а затем всё подробно разберем.
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: Поиск в ширину
Ресурсы
Комментарии (8)
Representative
05.11.2024 11:51Можно ли узнать, лучше ли использовать по общей эффективности алгоритм A*(возможно даже bidirectional), чем просто raw Дейкстра?
Или эти вещи не стоит сравнивать?
yastrebdev Автор
05.11.2024 11:51Я до вашего комментария не читал про A*. Но теперь могу предположить, что для поиска единственного лучшего пути больше подойдет A*. Спасибо за вопрос.
wataru
05.11.2024 11:51Это разные классы алгоритмов. Дейкстра ищет до всех вершин, а A* до одной конкретной. A* в этом случае обычно лучше. Правда, не везде и не всегда. Если эвристика не очень точная и долго вычисляемая, то Дейкстра будет даже быстрее A*.
wataru
05.11.2024 11:51Вот метод, как найти все кратчайшие пути (вы в другой статье спрашивали): cначала Дейкстрой найдите расстояния до всех вершин. Потом рекурсивным перебором из конца, идите в каждую вершину, если расстояние там + длина ребра = расстоянию тут. Когда дошли до начала выводите текущий путь задом на перед. Можно, кстати, упростить этот момент, если запускать Дейкстру не из начала в конец, а наоборот, из конца в начало. Тогда восстановленый путь не надо будет разворачивать. Ну, если у вас граф не ориентированный, конечно. В ориентированном надо сначала все ребра развернуть.
Учтите только, что различных путей кратчайшей длины может быть экспоненциально много, а в случае ребер нулевой длины - вообще бесконечное количество. Кстати, для ребер отрицательной длины дейкстра вообще не работает, про это стоило упомянуть в статье.
yastrebdev Автор
05.11.2024 11:51Спасибо вам. Хорошая задача что бы попрактиковаться. Для таких комментариев стоит писать и ошибаться)
wataru
Плохое объяснение. Особенно с учетом, что статьями про дейкстру завален интернет в целом и хабр в частности.
Вы воспроизводите самую большую ошибку комментариев - когда в них просто продублировано, что делает код:
По вашей статье невозможно понять алгоритм, только вызубрить. Ни слова про то, что он является по сути динамическим программированием, почему он работает, что его можно делать без очереди и так будет даже быстрее на плотных графах. Вообще, правильно сначала объяснить алгоритм без очереди, а потом уже ее сверху навешивать как оптимизацию.
yastrebdev Автор
Здравствуйте! Я с вами согласен. Это одна из моих первых статей и я разбираюсь на сколько умею. Мне нравится писать и параллельно понимать. В следующий раз постараюсь сделать лучше, а сейчас получилось вот так.
Ваши слова приму во внимание.