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

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

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

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

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

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

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

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

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

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

Подписаться

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

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

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

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

Напомню, что в прошлом разделе кратчайший путь от 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 — Поиск в ширину

Ресурсы

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

2. Редактор gif

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

© Habrahabr.ru