Алгоритм Дейкстры

Алгоритм Дейкстры

В предыдущей статье были рассмотрены сбалансированные деревья: Сбалансированные деревья. Здесь далее текст пойдёт о взвешенных графах и алгоритме Эдсгера Дейкстры.

В статье про поиск в ширину можно увидеть, как найти путь из точки А в точку В. Найденный путь не обязательно окажется самым быстрым. Этот путь считается кратчайшим только потому что состоит из наименьшего числа сегментов(рёбер). Но представим, что с каждым сегментом связывается продолжительность перемещения. И тогда может выясниться, что существует не самый кратчайший, но более быстрый путь.

Алгоритм поиска в ширину находит путь с минимальным количеством сегментов(рёбер у графа). А если необходимо найти самый быстрый путь? Быстрее всего его найти при помощи алгоритма Дейкстры.

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

Посмотрим на граф и как алгоритм Дейкстры поработает с таким графом.

Каждому ребру назначается время перемещения, например, в минутах. Алгоритм Дейкстры используется для поиска пути от начальной точки к конечной за кратчайшее возможное время. Применив к этому графу поиск в ширину, вы получите следующий кратчайший путь: начало → А → конец. Этот путь занимает 7 минут. А может существовать путь, который займёт меньше времени? Алгоритм Дейкстры состоит из четырёх шагов:

1. Найти узел с наименьшей стоимостью (т.е. узел, до которого можно добраться за минимальное время);
2. Обновить стоимости соседей этого узла;
3. Повторять, пока это не будет сделано для всех узлов графа;
4. Вычислить итоговый путь.

Шаг 1: найти узел с наименьшей стоимость. В самом начале выбираем, куда направиться: к узлу A или узлу B? Сколько времени необходимо, чтобы добраться до каждого из этих узлов?

До узла A – 7 минут, а до узла B – 3 минуты. Что касается остальных узлов, о них алгоритм пока ничего не знает. Так как время достижения конечного узла остаётся неизвестным, считается, что оно бесконечно. Узел B – ближайший, т.к. до него всего 3 минуты.

Шаг 2: вычислить, сколько времени потребуется для того, чтобы добраться до всех внешних соседей B при переходе по ребру из B. При этом обнаруживается более короткий путь к узлу A. Ранее до перехода к нему требовалось 7 минут, теперь же 6.

Если находится таким способом, более короткий путь для соседа B, то необходимо обновить его стоимость. В данном случае найдено:

• более короткий путь к A (сокращение с 7 до 6 минут);
• первый путь к конечному узлу до 8 минут.

Шаг 3: повторение.

Снова выполняется шаг 1. С узлом B работа закончена, поэтому наименьшая оценка по времени производится по узлу A.

Снова выполняется шаг 2. Обновляем стоимости внешних соседей для узла A. Алгоритм вычисляет, что путь до конечного узла теперь занимает 7 минут! Алгоритм на этом завершается. К моменту завершения работы алгоритма становится известно:

• Чтобы добраться до узла B, нужно 3 минуты;
• Чтобы добрать до узла A, нужно 6 минут;
• Чтобы добраться до конечного узла, нужно 7 минут.

Последний шаг – вычисление итогового пути(разберёмся с ним ниже). А пока просто посмотрим как выглядит итоговой путь:

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

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

Терминология

Разберёмся с терминологией. Когда используется алгоритм Дейкстры, с каждым ребром графа связывается число, называемое весом.

Граф с весами называется взвешенным графом. Граф без весов называется невзвешенным графом. Для вычисления кратчайшего пути в невзвешенном графе используется алгоритм поиска в ширину. Кратчайшие пути во взвешенном графе вычисляются по алгоритму Дейкстры.

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

Наконец, существует понятие направленных и ненаправленных графов. Само понятие ненаправленного графа означает, что каждый из двух узлов соединённых путём фактически ведёт к другому узлу. Это может быть и цикл. В ненаправленном графе каждое новое ребро добавляет ещё один цикл. Алгоритм Дейкстры работает только с графами, в которых нет циклов и где все рёбра неотрицательны.

Далее речь пойдёт о ребрах с положительными весами.

История одного обмена

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

Узлы графа – это предметы, на которые можно поменяться. Веса рёбер представляют сумму доплаты за обмен. Таким образом, можно поменять картину на гитару за 300 рублей или же куртку на гитару за 150 рублей(условные суммы).

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

Для вычисления итогового пути добавляется столбец – родитель. Итак, приступим к выполнению алгоритма:

Шаг 1: найти узел с наименьшей стоимостью. В данном случае самый дешёвый вариант обмена с доплатой 0 рублей это картина. Возможно ли получить картину с меньшими затратами? Это очень важный момент. Удастся ли найти серию обменов, при которой мы получим картину менее чем за 0 рублей(точнее нам ещё заплатят)? Правильный ответ: в данном графе это не удастся. Так как картина это узел с наименьшей стоимостью, до которого можно добраться и снизить его заданную стоимость нельзя. В этом заключается суть и идея алгоритма Дейкстры: в графе ищется всегда путь с наименьшей стоимостью. Пути к этому с картиной с меньшими затратами не существует!

Шаг 2: вычислить, сколько времени потребуется для того, чтобы добраться до всех соседей(стоимость).

Стоимости гитары и барабана заносятся в таблицу. Они были заданы при переходе через узел картины, поэтому картина указывается как их родитель. Это означает, что для того, чтобы добраться до гитары, вы проходите по ребру от картины; то же самое происходит с барабаном.

Снова шаг 1: куртка – следующий по стоимости узел(50 рублей).

Снова шаг 2: обновляются значения всех его соседей.

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

Следующий по стоимости узел – гитара. Обновите данные его соседей.

Наконец-то мы вычислили стоимость для планшета при условии обмена гитары на планшет. Соответственно, гитара назначается родителем. Наконец, задается стоимость последнего узла – барабана.

Оказывается, вы можете получить планшет дешевле, поменяв барабан на планшет. Таким образом, самая дешёвая цепочка обменов обойдётся в 350 рублей.

Теперь, осталось вычислить итоговый путь. К этому моменту мы(алгоритм) знаем, что кратчайший путь обойдётся в 350 рублей, но как этот путь определить?

Для начала возьмём родителя для узла "планшет". В качестве родителя узла "планшет" указан узел "барабан". А в качестве родителя узла "барабан" указан узел "куртка". Следовательно, вы обмениваете куртку на барабан. И конечно, в самом начале вы меняете книгу на куртку. Проходя по родительским узлам в обратном направлении получается полный путь:

Целью этого примера было показать, что кратчайший путь не всегда связывается с физическим расстоянием: он может решать задачу минимизации какой-либо характеристики благодаря тому же алгоритму Дейкстры!

Рёбра с отрицательным весом

Изменим пример выше. Предположим, что существует обмен куртки на картину и при этом вам ещё заплатят 70 рублей. Вы ничего не тратите при таком обмене, вместо этого вы наоборот получаете! Изобразим это на графе:

Ребро, ведущее от куртки к картине, имеет отрицательный вес! Получается также, что к картине можно добраться двумя способами. А значит что на обмене с отрицательным весом(когда платите не вы, а вам) появляется смысл – вы получите ещё 20 рублей от начальной суммы. Теперь, если вы помните, вы можете обменять картину на барабан. И до этого обмена существуют два пути: Второй путь обойдётся на 20 рублей дешевле, поэтому нужно выбрать этот путь. Но если применить алгоритм Дейкстры к этому графе, то алгоритм выберет неверный путь! Алгоритм пойдёт по более длинному пути. Алгоритм Дейкстры не может использоваться при наличии рёбер, имеющих отрицательный вес. Такие рёбра нарушают работу алгоритма Дейкстры. Посмотрим на пример: начиная с таблицы стоимостей.

Теперь найдём узел с наименьшей стоимостью и обновим стоимости его соседей. В этом случае картина оказывается узлом с наименьшей стоимостью. В соответствии с алгоритмом Дейкстры, к картине невозможно перейти более дешёвым способом, чем обменом её на вашу книгу(а видя весь граф вы знаете что это неверно!). Как бы то ни было, продолжая пример обновим стоимости соседей картины.

Получается, что теперь стоимость барабана составляет 350 рублей. Перейдём к следующему по стоимости узлу, который ещё не был обработан – это куртка. Обновим стоимости её соседей.

Узел "картина" уже был обработан, однако алгоритм обновляет его стоимость. Это очень плохой признак – обработка узла означает, что к нему невозможно добраться с меньшими затратами. Но вы самостоятельно уже нашли более "дешёвый" путь к картине. У барабана соседей нет, поэтому работа алгоритма завершается. Ниже покажем итоговые стоимости согласно алгоритму Дейкстры:

Чтобы добраться до барабана, вам потребовалось 350 рублей. Вы знаете, что существует путь, который стоит всего 330 рублей, но алгоритм Дейкстры его не находит. Алгоритм Дейкстры сразу предположил, что, поскольку вы обрабатываете узел "картина", к этому узлу невозможно добраться быстрее! Это предположение работает только в том случае, если рёбер с отрицательным весом не существует. Следовательно, использование алгоритма Дейкстры с графом, содержащим рёбра с отрицательным весом — невозможно. В случае с отрицательными весами понадобится алгоритм Беллмана — Форда. Рассмотрение алгоритма Беллмана — Форда выходит за рамки этой статьи. Займёмся теперь реализацией алгоритма Дейкстры.

Реализация алгоритма Дейкстры

Ниже изображён граф, который будет использоваться в примере с кодом:

Для реализации понадобятся три хеш-таблицы или три словаря в Python. Словари стоимостей и родителей будут обновляться по ходу работы алгоритма. Сначала необходимо реализовать словарь для графа:

graph = {}

Необходимо сохранить соседей и стоимость перехода. Судя по графу у начального узла есть два соседа, A и B. Веса рёбер графа также представим виде хеш-таблицы или словаря:

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

Итак, graph["start"] является словарём. Для получения всех соседей узла можно воспользоваться следующим выражением:

print(list(graph["start"].keys()))
# ["a", "b"]

Одно ребро ведёт из начального узла в A, а другое из начального узла в B. Веса узнать этих рёбер можно так:

print(graph["start"]["a"]) # 6
print(graph["start"]["b"]) # 2

Допишем в граф остальные узлы:

graph["a"] = {}
graph["a"]["final"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["final"] = 5
graph["final"] = {}  # У конечного узла соседей нет

Стоимость узла определяет, сколько времени потребуется для перехода к этому узлу от начального узла. Вы не знаете, сколько времени потребуется для достижения конечного узла. Если стоимость ещё неизвестна, она считается бесконечной. Как представить бесконечно в Python? Есть следующий вариант: infinity = math.inf. Код создания словаря стоимостей:

import math
infinity = math.inf
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["final"] = infinity

Для родителей также создадим отдельный словарь. Код представлен ниже:

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["final"] = None

Наконец, нужно множество для отслеживания всех уже обработанных узлов, так как один узел не должен обрабатываться многократно:

processed = set()

На этом подготовка для данных завершена. Ниже напишем код алгоритма:

node = find_lowest_cost(costs) # Найти узел с наименьшей стоимостью среди необработанных
while node is not None: # Обрабатываем все узлы
  cost = costs[node] # Получить стоимость
  neighbors = graph[node] # Получить соседей узла
  for n in neighbors.keys(): # Перебор всех соседей текущего узла
    new_cost = cost + neighbors[n] # Вычисляем стоимость пути перехода
    if costs[n] > new_cost: # Если к соседу можно добрать быстрее через текущий узел
      costs[n] = new_cost # Обновить стоимость узла
      parents[n] = node # Этот узел становится новым родителем для соседа
  processed.add(node) # Узел помечается как обработанный
  node = find_lowest_cost(costs) # Найти следующий узел для обработки

После того как все узлы будут обработаны, алгоритм завершается. Код функции find_lowest_cost(costs) приведём ниже:

def find_lowest_cost(costs):
  lowest_cost = math.inf
  lowest_cost_node = None
  for node in costs: # Перебираем все узлы
    cost = costs[node]
    if cost < lowest_cost and node not in processed: # Если узел с наименьшей стоимость и ещё не был обработан
      lowest_cost = cost # он назначается новым узлом с наименьшей стоимостью
      lowest_cost_node = node
  return lowest_cost_node

Чтобы найти узел с наименьшей стоимостью, мы каждый раз перебираем все узлы. Существует более эффективный вариант этого алгоритма. Он использует структуру данных, называемую очередью с приоритетом. Эта очередь строится на основе другой структуры данных — кучи. Если вам интересны очереди с приоритетом и кучи, об этом будет далее статья.

Объединим весь код:

import math

graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["final"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["final"] = 5
graph["final"] = {}

infinity = math.inf
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["final"] = infinity

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["final"] = None

processed = set()

def find_lowest_cost(costs):
  lowest_cost = math.inf
  lowest_cost_node = None
  for node in costs:
    cost = costs[node]
    if cost < lowest_cost and node not in processed:
      lowest_cost = cost
      lowest_cost_node = node
  return lowest_cost_node

node = find_lowest_cost(costs)
while node is not None:
  cost = costs[node]
  neighbors = graph[node]
  for n in neighbors.keys():
    new_cost = cost + neighbors[n]
    if costs[n] > new_cost:
      costs[n] = new_cost
      parents[n] = node
  processed.add(node)
  node = find_lowest_cost(costs)

print("Стоимость от начала до каждого узла:")
print(costs)

В следующей статье информация про жадные алгоритмы.

Попробуйте сами скопировать и запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.