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

Теперь вы, как специалист на посту разработчика 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. Пособие по алгоритмам

Комментарии (8)


  1. wataru
    05.11.2024 11:51

    Плохое объяснение. Особенно с учетом, что статьями про дейкстру завален интернет в целом и хабр в частности.

    Вы воспроизводите самую большую ошибку комментариев - когда в них просто продублировано, что делает код:

    # присваиваем 10 в переменную a
    a = 10

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


    1. yastrebdev Автор
      05.11.2024 11:51

      Здравствуйте! Я с вами согласен. Это одна из моих первых статей и я разбираюсь на сколько умею. Мне нравится писать и параллельно понимать. В следующий раз постараюсь сделать лучше, а сейчас получилось вот так.

      Ваши слова приму во внимание.


  1. Representative
    05.11.2024 11:51

    Можно ли узнать, лучше ли использовать по общей эффективности алгоритм A*(возможно даже bidirectional), чем просто raw Дейкстра?

    Или эти вещи не стоит сравнивать?


    1. yastrebdev Автор
      05.11.2024 11:51

      Я до вашего комментария не читал про A*. Но теперь могу предположить, что для поиска единственного лучшего пути больше подойдет A*. Спасибо за вопрос.


    1. wataru
      05.11.2024 11:51

      Это разные классы алгоритмов. Дейкстра ищет до всех вершин, а A* до одной конкретной. A* в этом случае обычно лучше. Правда, не везде и не всегда. Если эвристика не очень точная и долго вычисляемая, то Дейкстра будет даже быстрее A*.


      1. Representative
        05.11.2024 11:51

        Спасибо.


  1. wataru
    05.11.2024 11:51

    Вот метод, как найти все кратчайшие пути (вы в другой статье спрашивали): cначала Дейкстрой найдите расстояния до всех вершин. Потом рекурсивным перебором из конца, идите в каждую вершину, если расстояние там + длина ребра = расстоянию тут. Когда дошли до начала выводите текущий путь задом на перед. Можно, кстати, упростить этот момент, если запускать Дейкстру не из начала в конец, а наоборот, из конца в начало. Тогда восстановленый путь не надо будет разворачивать. Ну, если у вас граф не ориентированный, конечно. В ориентированном надо сначала все ребра развернуть.

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


    1. yastrebdev Автор
      05.11.2024 11:51

      Спасибо вам. Хорошая задача что бы попрактиковаться. Для таких комментариев стоит писать и ошибаться)