Алгоритм Дейкстры для поиска кратчайшего пути в Python

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

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

Что делает алгоритм Дейкстры

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

Создание графа для алгоритмы Дейкстры

Важно понимать, граф представляет собой множество узлов (nodes), соединенных ребрами (edges).

Граф алгоритм Дейкстры

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

Как узлы, так и ребра могут быть носителями информации. К примеру, граф выше представляет собой систему зданий, которые соединены между собой туннелями. В узлах может находиться информация о названии здания (например, строка «Библиотека»), в то время, как ребро может содержать информацию о длине туннеля.

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

Реализация графов в Python

Данный этап немного выходит за рамки темы, рассматриваемой в статье, поэтому мы не будем вдаваться в подробности. Два самых популярных способа реализации графа — через матрицу смежности или через список смежности. У каждого метода есть свои преимущества и недостатки. Сначала рассмотрим реализацию через матрицу смежности, так как его проще представить визуально и понять на интуитивном уровне. Позже станет яснее, отчего определение базовой реализации оказывает сильное влияние на время выполнения. Любая реализация может задействовать алгоритм Дейкстры, а пока важно различать API, или абстракции (методы), которые могут взаимодействовать с графом. Кратко осветим реализацию матрицы смежности на примере кода Python. Для ознакомления с реализацией списка смежности хорошим стартом станет данная статья.

Ниже представлена матрица смежности для предыдущего графа. Каждый ряд представляет один узел графа, как и каждый столбец. В данном случае ряд 0 и столбец 0 представляют узел «А»; ряд 1 и столбец 1 — узел «B», ряд 2 и столбец 2 — узел «C» и так далее, принцип понятен. Каждый локальный элемент {ряд, столбец} представляет ребро. Таким образом, каждый ряд показывает связь между одним узлом и всеми прочими узлами. Элемент «0» указывает на отсутствие ребра, в то время как «1» указывает на присутствие ребра, связывающего row_node и column_node в направлении row_node → column_node. Поскольку граф в примере является неориентированным, данная матрица равна его транспонированию (то есть матрица симметричная), поскольку каждая связь двунаправленная. Вы могли заметить, что главная диагональ матрицы представлена только нулями, а все оттого, что ни один узел не связан сам с собой. Таким образом, пространственная сложность данного представления нерасчетлива.

Матрица смежности для графа

Теперь разберемся с кодом. Обратите внимание, что здесь задействовано немного экстра-данных — так как нам было нужно, чтобы реальные объекты узлов содержали определенную информацию, в классе Graph был реализован массив объектов узлов, индексы которых соответствуют номеру их ряда (столбца) в матрице смежности. В Graph также был добавлен вспомогательный метод, который позволяет использовать либо номера индекса узла, либо объект узда в качестве аргументов для методов класса Graph. Данные классы нельзя считать примерами элегантности, однако они хорошо выполняют свою работу, излишне не усложняя процесс:

Здесь классы Node и Graph будут использованы для описания данного примера графа. Поместим вышеуказанный граф в код и посмотрим, получится ли в итоге верная матрица смежности:

Матрицы смежности, полученная в выводе (из graph.print_adj_mat()) после запуска кода, такая же, как и та, что была рассчитана ранее:

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

В результате выводится следующая матрица смежности:

Визуально данный граф будет представлен следующим образом:

Граф матрица смежности

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

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

Перед непосредственным составлением кода, осветим ключевые моменты темы:

  1. Главное условие: отрицательных длин ребер не бывает.
  2. Алгоритм Дейкстры изначально создавался для поиска кратчайшего пути между двумя конкретными узлами. Однако сегодня он также широко используется для поиска кратчайших путей между узлом источника и всеми остальными узлами. В статье будет рассмотрен второй вариант. Для осуществления первого случая понадобится просто остановить алгоритм сразу после того, как узел назначения будет добавлен в набор seen. По ходу дела все станет намного понятнее.

Окей, примемся за дело. Нам нужно найти исходным узлом и всеми другими узлами (или узлом назначения), однако проверять КАЖДУЮ возможную комбинацию отправления-назначения не хочется. При наличии крупного графа на это потребуется огромное количество времени, и большая часть проверенных путей в конечном итоге окажется ненужной. По этой причине, пойдем напролом и задействуем жадный подход. Наслаждайтесь моментом, ведь это тот редкий случай, когда жадность будет вознаграждена.

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

Скажем, мы находимся в исходном узле. Предположим, что начальное предварительное расстояние от узла источника до каждого другого узла в графе является бесконечностью (перепроверим позже). Известно, что по умолчанию расстояние от узла источника до этого же узла источника минимально (0), ведь отрицательных длин ребер быть не может. Наш исходный узел осматривает все соседние узлы и обновляет предварительное расстояние от узла источника до длины ребра от узла источника до конкретного соседнего элемента (плюс 0). Обратите внимание, что НУЖНО проверить каждого ближайшего соседа, этого никак не пропустить. Затем алгоритм делает тот самый жадный выбор для следующей оценки узла, который находится на ближайшем расстоянии к источнику. У нас исходный узел отмечен как visited, поэтому к нему можно не возвращаться и сразу перейти к следующему узлу.

Теперь задумаемся, где мы сейчас находимся в плане логики, так как это важно для реализации. Узел, что сейчас оценивается (ближайший к источнику) больше НИКОГДА не будет оцениваться вновь в плане кратчайшего пути от исходного узла. Его предварительное расстояние теперь стало точным расстоянием. Хотя вполне возможно, что пути от исходного узла к данному узлу могут проходить через иные маршруты, можно с уверенностью сказать, что они будут затратнее, нежели текущий путь. Он был выбран ввиду того, что был кратчайшим по сравнению с любым другим узлом, связанным с источником. Следовательно, любой другой путь будет длиннее, чем текущее расстояние от исходного узла до рассматриваемого узла.

При использовании графика из примера в случае установки исходного узла как А, мы бы назначили предварительные расстояния для узлов B, C и E. Поскольку у E было кратчайшее расстояние от A, после этого был посещен узел E. И теперь, хотя наверняка есть несколько других способов добраться из А до Е, они будут затратнее, нежели текущее расстояние АЕ. Другие маршруты должны проходить через B или С, а в результате проверки стало ясно, что они дальше от A, чем E. Жадный выбор был сделан, а это ограничивает общее количество проверок, которые нам нужно сделать, и при этом точность не теряется. Неплохо.

Продолжим логическую цепочку с использованием графа из примера. Просто повторим для E действия, сделанные для A. Обновляются все ближайшие соседние элементы к E с предварительным расстоянием, равным length(A у E) + edge_length(E к соседнему элементу). Это верно в том случае, ЕСЛИ данное расстояние меньше, чем текущее предварительное расстояние, или же предварительное расстояние еще не было установлено.

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

Далее делается жадный выбор касательно того, какой узел должен оцениваться следующим. Выбирается один узел из графа с наименьшим предварительным расстоянием, и добавляется E к набору seen nodes. Теперь он повторно оцениваться не будет. У данного нового узла та же гарантия, что что и E — его предварительное расстояние от A является определенным минимальным расстоянием от A. Чтобы понять это, давайте оценим возможности (хотя они могут не соответствовать графу примера, для ясности используем те же названия). Если следующий узел является соседом E, но не A, то он будет выбран, потому что его временное расстояние все еще короче, чем любого другого прямого соседа A. По этой причине нет другого возможного кратчайшего пути, только через E. Если следующий выбранный узел будет непосредственным соседом A, то есть вероятность, что этот узел обеспечит более короткий путь к некоторым из соседей E, чем сам E.

Обзор кода алгоритма Дейкстры на Python

Давайте более четко и формально рассмотрим процесс реализации алгоритма Дейкстры.

ИНИЦИАЛИЗАЦИЯ

  1. Установите provisional_distance для всех узлов от исходного узла до бесконечности.
  2. Определите пустой набор seen_nodes. Данный набор гарантирует, что узел, у которого уже есть кратчайший путь, не будет повторно рассмотрен, а также то, что не будут рассматриваться пути через узел, у которого более короткий путь к источнику, чем текущий путь. Помните, что узлы входят в seen_nodes только после доказательства того, что в наличии есть абсолютное кратчайшее расстояние (а не только предварительное расстояние). Набор используется для получения времени поиска O(1) вместо многократного выполнения поиска через массив O(n).
  3. Установите provisional_distance для исходного узла со значением 0, и массив, представляющий перескоки для простого включения самого исходного кода. Это будет полезно позже, когда мы проследим выбранный для графа путь для расчета минимального расстояния.

ПРОЦЕДУРА ИТЕРАЦИИ

  1. Пока (while) все узлы увидеть (seen) не удалось. Или, в случае поиска одного узла назначения, пока не удалось увидеть (seen) данный узел назначения.
  2. Установите current_node для узла c самым малым предварительным расстоянием provisional_distance во всем графе. Обратите внимание, что для первой итерации это будет исходный узел source_node, так как предварительное расстояние provisional_distance установлено на 0.
  3. Добавьте текущий узел current_node к набору просмотренных узлов seen_nodes.
  4. Обновите provisional_distance каждого соседнего элемента current_node до (абсолютного) расстояния от current_node до source_node вдобавок к длине ребра от current_node к данному соседнему элементу, ЕСЛИ данное значение меньше, чем текущее значение соседнего provisional_distance. Если у соседнего элемента еще не было набора предварительного расстояния, помните, что он инициализирован до бесконечности, и по этой причине должен быть больше, чем данная сумма. При обновлении provisional_distance также обновляются «перескоки», которые были сделаны для получения расстояния, задействуя конкатенацию перескоков current_node к исходному узлу с самим current_node.
  5. Завершение цикла while.

Алгоритм Дейкстры через схемы и изображения

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

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

Обратите внимание, что в дальнейшем можно посетить либо D, либо B. Сейчас мы посетим B.

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

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

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

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

Здесь программа завершается. В результате мы получаем кратчайшие пути для каждого узла графа.

Python код для алгоритма Дейкстры

Посмотрим, как будет выглядеть реализация алгоритма Дейстры в Python. Это экземпляр метода внутри раннее используемого класса Graph, который задействует преимущества других методов и структуры:

При использовании данного метода можно протестировать нашу картинку:

Для получения читабельного для людей вывода нужно отметить объекты узла в их data. Результат станет следующим:

Здесь каждый кортеж(total_distance, [hop_path]). Это совпадает с рассматриваемой картинкой.

Быстрый способ реализации алгоритма Дейкстры в Python

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

Остановимся на одном довольно важном моменте. В каждой итерации нам нужно найти узел с кратчайшим предварительным расстоянием, что требуется для следующего жадного решения. Сейчас осматривается list, вызывая queue (используя данные значения в dist) с целью получения желаемого. У данного queue может быть максимальная длина n, что является числом узлов. Итерация по этому списку является операцией O(n), которую мы выполняем в каждой итерации цикла while. Так как цикл while продолжается до тех пор, пока не будет просмотрен (seen) каждый узел, сейчас операция O(n) совершается n раз. Наш алгоритм — O(n2). Это не очень хорошо, но и это не все.

Если взглянуть на реализацию матрицы смежности в Graph, можно заметить, что для нахождения связи нам пришлось осмотреть весь ряд (размера n). Это еще одна операция O(n) в цикле while. Как это исправить? Во-первых, можно использовать кучу для получения минимального предварительного расстояния в O(lg(n)) времени вместо O(n) времени (при бинарной куче — отметьте, что куча Фибоначчи способна на это в O(1)). Во-вторых, можно реализовать граф при помощи списка смежности, где у каждого узла есть список связанных узлов. Получается, что осматривать все узлы на наличие существующей связи не потребуется. Это показывает, почему важно понимать то, как мы представляем структуры данных. В случае реализаци кучи при помощи представления матрицы смежности асимптомическое время выполнения запуска алгоритма изменено не будет. (На заметку: Если вам не знакома нотация big-O, можете просмотреть данную статью).

Кучи в Python

Такая структура данных, как куча, обычно используется для реализации очереди с приоритетом. По сути, они эффективны во время ситуаций, когда нужно быстро получить элемент с наивысшим приоритетом. В нашем случае элемент с высоким приоритетом — это наименьшее предварительное расстояние (provisional distance) от оставшихся нерассмотренных узлов. Вместо того, чтобы каждый раз осматривать весь массив в поисках наименьшего предварительного расстояния (provisional distance), можно использовать находящуюся там кучу, что готова передать узел с наименьшим предварительным расстоянием (provisional distance). Как только расстояние будет извлечено из кучи, она быстро перестоится, будучи готовой к передаче нового значения в тот момент, когда оно будет нужно. Довольно неплохо! Для практики можете попробовать реализовать очень быструю Фибоначчиеву кучу. А далее мы попробуем реализовать Binary MinHeap, что поможет разрешить наши задачи.

По сути бинарная куча является полным бинарным деревом, что обладает свойством кучи. Что это значит?

Полное бинарное дерево — это структура в виде дерева данных, где у КАЖДОГО родителя узла есть ровно два дочерних узла. Если дочерних узлов недостаточно, чтобы в последнем ряду родительских узлов было по 2 дочерних узла, дочерние узлы будут заполняться слева направо.

Как это будет выглядеть?

Полное бинарное дерево

Свойство кучи (для минимальной кучи) Каждый родитель ДОЛЖЕН быть меньше или равен обоим дочерним элементам.

Применив данный принцип к указанному выше полному бинарному дереву, мы получим следующий результат:

Целое бинарное дерево

Здесь представлен базовый массив [2, 5, 4, 7, 9, 13, 18]. Как видите, сортировка сделана наполовину, но в данном случае нам и не нужна полная сортировка. Через минуту данный базовый массив станет намного понятнее.

Теперь у нас есть представление о том, что из себя представлят куча. Напишем код и посмотрим, как используются дополнительные методы для реализации требуемых пользователю действий.

Так как бинарная куча является специальной реализацией бинарного дерева, начнем с создания класса BinaryTree, у которого будет наследовать рассматриваемая куча. Для реализации бинарного дерева нужно создать базовую структуру данных в виде массива, после чего структура дерева будет рассчитана через индексы узлов внутри массива. К примеру, у начального бинарного дерева (первое изображение полного бинарного дерева) базовый массив будет [5, 7, 18, 2, 9, 13, 4]. Мы обозначим связи между узлами при определении индекса узла в базовом массиве. Известно, что у каждого родителя ровно два дочерних элемента. Нулевой индекс является корнем в основе, индекс 1 — левый ребенок, а индекс 2 — правый ребенок. Если обобщить, левый ребенок индекса i будет обладать индексом 2*i + 1, а правый — 2*i + 2. У узла индекса i родительский индекс — floor((i-1) / 2).

Итак, класс BinaryTree будет выглядеть следующим образом:

Теперь MinHeap может наследовать BinaryTree и задействовать требуемую функциональность. Теперь BinaryTree можно будет вновь использовать в иных контекстах.

Окей, мы практически у финала. Сейчас нужно будет идентифицировать способности класса, который должны быть у класса MinHeap, а затем реализовать их. Необходимо, чтобы куча могла:

  • Измениться, вместо неупорядученного бинарного дерева став минимальной кучей. Это делается через конкретизацию кучи;
  • Получите минимальное значение, а затем реструктурироваться для сохранения своих свойств. Это будет использоваться при посещении следующего узла;
  • Обновить (уменьшить) значение узла, сохранив свойство кучи. Это будет использоваться при обновлении предварительных расстояний.

Для осуществления данных условий начнем с создания блока, который сыграет важную роль при реализации первых двух функций. Напишем метод под названием min_heapify_subtree. Данный метод будет рассматривать всю кучу как heapified (то есть при этом поддерживая свойство кучи), кроме единственного узла 3-го поддерева. Мы будем рекурсивно накапливать это поддерево, идентифицируя его индекс родительского узла в точке i и давая возможность правильно размещенному узлу найти верную позицию в куче. Для этого проверяем, меньше ли дочерние узлы, чем родительский. Если да, заменяем наименьший дочерний узел с родительским. Затем рекурсивно вызываем метод по индексу замененного родителя (который теперь является дочерним), чтобы убедиться, что он помещен в позицию для поддержки свойства кучи. Вот псевдокод:

В худшем случае метод начинается с индекса 0 и рекурсивно распространит корневой узел вплоть до нижнего листа. Поскольку здесь куча является бинарным деревом, у нас есть уровни lg(n), где n — общее количество узлов. Поскольку каждая рекурсия метода выполняет фиксированное количество операций, то есть O(1), классификация времени выполнения min_heapify_subtreeO(lg (n)).

Для превращения совершенно случайного массива в правильную кучу, просто нужно вызвать min_heapify_subtree на каждом узле, начиная с нижних листьев. Задействуем метод min_heapify:

Данный метод выполняет метод O(lg(n)) n раз, поэтому его время выполнения будет O(n*lg(n)).

Нам нужно извлечь минимальное значение из кучи. Значение можно принять время за O(1), потому что оно всегда будет корневым узлом минимальной кучи (т.е. индекс 0 базового массива), но просто прочитать недостаточно. Требуется удаление, А ТАКЖЕ подтверждение того, что куча остается нагроможденной. Для этого удаляем корневой узел и заменяем его последним листом, а затем min_heapify_subtree индексом 0, чтобы обеспечить сохранение свойства кучи:

Метод выполняется за постоянное время, за исключением min_heapify_subtree. Можно сказать, что этот метод также O(lg (n)).

Отлично! На последнем этапе нужно будет добиться получения возможности обновления значний кучи (уменьшать их, поскольку обновляются предварительные расстояния (provisional distance) до более низких значений), сохраняя свойство кучи.

Итак, создадим метод под названием decrease_key, который принимает значение индекса обновляемого узла и новое значение. Мы хотим обновить значение этого узла, а затем добавить его туда, где он должен будет находиться, если станет меньше родителя. Таким образом, пока он не станет меньше родительского узла, поменяем его на родительский узел:

Окей, посмотрим, как все вышеперечисленное будет выглядеть в виде кода на Python:

Хорошо, время для последнего шага. Теперь уже точно! Нам просто нужно выяснить, как внедрить структуру данных MinHeap в метод dijsktra в Graph, который теперь должен быть реализован с помощью списка смежности. Нужно реализовать его, полностью используя преимущества среды выполнения кучи, при этом поддерживая класс MinHeap настолько гибким, насколько это возможно. Это нужно для повторного использования в будущем.

Итак, сначала разберемся с реализацией списка смежности. Вместо матрицы, представляющей соединения между узлами, требуется, чтобы каждый узел соответствовал списку узлов, к которым он подключен. Таким образом, если мы выполняем итерацию по соединениям узла, нам не нужно проверять ВСЕ узлы, чтобы увидеть, какие из них подключены — в списке этого узла находятся только подключенные узлы.

Уже знакомый нам граф:

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

Список смежности графа будет выглядеть приблизительно следующим образом:

Как видите, для получения определенной связи узлов нам больше не нужно проверять ВСЕ прочие узлы. Оставим API относительно простым, ради ясности оставим класс простым:

Далее сосредоточимся на реализации кучи для достижения лучшего алгоритма, чем текущий алгоритм O(n²). Если вспомним метод dijsktra, в классе Graph матрицы смежности, то увидим, что мы перебираем всю очередь, чтобы найти минимальное предварительное расстояние provisional distance (время выполнения O(n)), используя узел с минимальным значением для установки текущего посещаемого узла. Затем перебираем все соединения узла и при необходимости сбрасываем их предварительное расстояние provisional distance (проверьте метод connections_to или connections_from; вы увидите, что его время выполнения O(n)). Эти два алгоритма O(n) сводятся к времени выполнения O(n), потому что O(2n) = O (n). Делаем это для каждого узла графа, поэтому выполняем O(n) алгоритм n раз, тем самым получая время выполнения O(n²). Вместо этого сокращаем время выполнения до O((n + e) lg (n)), где n — количество узлов, а e — количество ребер.

В реализации списка смежности внешнему циклу while все еще нужно выполнять итерацию по всем узлам (n итераций), но чтобы получить ребра для текущего узла внутренний цикл просто должен итерировать ТОЛЬКО по ребрам для данного конкретного узла. Таким образом, внутренний цикл, повторяющийся по краям узла, будет выполняться только O(n + e) раз. Внутри данного внутреннего цикла нужно обновить предварительное расстояние для каждого из связанных узлов. Для этого будет использован метод decrease_key кучи, который мы уже рассматривали, как O(lg (n)). Таким образом, общее время выполнения будет равно O((n + e) lg (n)).

Новый алгоритм:

ИНИЦИАЛИЗАЦИЯ

  1. Установите provisional_distance всех узлов от источника до бесконечности, за исключением нашего исходного узла, значением которого будет 0. Добавьте данные к минимальной куче.
  2. Вместо сохранения набора seen_nodes определите, есть ли у вас осмотренные узлы. Это будет зависеть от того, что осталось в куче. Помните, что при использовании pop() для узла, он удаляется из кучи. Следовательно, в соответствии с логикой он будет рассматриваться, как «увиденный».

ПРОЦЕДУРА ИТЕРАЦИИ

  1. Цикл while выполняется до тех пор, пока куча > 0: (выполняется n раз)
  2. Установите current_node для возвращения значения heap.pop().
  3. Для n в current_node.connections используйте heap.decrease_key, если данная связь все еще в куче (то есть не была рассмотрена), А ТАКЖЕ если текущее значение provisional distance больше, чем предварительное расстояние current_node вместе с весом соседнего элемента. Данный цикл for в общем будет выполняться n + e раз, а его временную сложность можно представить, как O(lg(n)).
  4. Конец цикла while.

Есть две задачи, которые нужно решить при данной реализации:

Задача 1: Код написан таким образом, что куча работает с массивом чисел. Однако нам нужна инкапсуляция предварительного расстояния provisional distance (метрики, которая использовалась при преобразовании в кучу), перескоков И узла, которому соответствует расстояние.

Задача 2: Нужно проверить, находится ли узел внутри кучи, А ТАКЖЕ обновить его provisional distance, используя метод decrease_key, для которого требуется индекс данного узла в куче. Для сохранения своих свойств куча постоянно меняет индексы. Нужно убедиться, что данная задача не будет решена простым анализом кучи в поисках точного места узла. Данная операция O(n) будет выполняться (n + e) раз, следовательно, создание кучи и реализация списка смежности ни к чему не приведут, ведь нам нужно со всем управиться за O(1) раз.

Решение 1: Нам нужно сохранить реализацию кучи максимально гибкой. Чтобы принимать любой тип данных в качестве элементов в базовом массиве, можно просто принять необязательные анонимные функции (например, лямбда-выражения) при создании экземпляра, которые предоставляются пользователем, чтобы указать, как он должен обращаться с элементами внутри массива, если эти элементы не являются простым целым числом. Значением по умолчанию для лямбд может быть функция, которая работает, если элементы массива являются просто числами. Таким образом, если требуется простая куча с числами, пользователю не нужно вставлять лямбды. Данные настраиваемые процедуры потребуются для сравнения элементов, а также для возможности уменьшить значение элемента. Можно назвать лямбду сравнения is_less_than, и ее значение по умолчанию должно быть: a, b: a < b. Лямбда-функция для возврата обновленного узла с новым значением может называться update_node, и ее значение по умолчанию должно быть просто lambda node, newval: newval. При передаче узла и нового значения пользователю дается возможность определить лямбду, которая обновляет существующий объект ИЛИ заменяет значение, которое там находится. В контексте реализации старого Graph, поскольку узлы имели бы значения [ provisional_distance, [nodes, in, hop, path]] лямбда is_less_than могла бы выглядеть следующим образом: lambda a,b: a[0] < b[0].  Здесь можно было бы оставить значение второй лямбды по умолчанию и передать вложенный массив в decrease_key.

Тем не менее, вскоре станет ясно, что существует довольно простое решение вопроса, при котором создаются настраиваемые объекты узлы node и передаются в MinHeap. Гибкость, которая недавно упоминалась, позволит легко воплотить это элегантное решение. В частности, в приведенном ниже коде вы увидите, что лямбда is_less_than превратиться в: lambda a, b: a.prov_dist < b.prov_dist, а лямбда update_node станет: lambda node, data: node.update_data (data), что намного аккуратнее использования вложенных массивы.

Решение 2: Есть несколько способов решить данную задачу, но давайте попробуем выбрать тот, который идет рука об руку с Решением 1. Учитывая гибкость, которой мы добились в Решении 1, мы можем продолжать использовать эту стратегию для реализации дополняющего решения и здесь. Можно реализовать дополнительный массив внутри класса MinHeap, который отображает исходный порядок вставленных узлов в их текущий порядок внутри массива узлов. Назовем этот список order_mapping. Поддерживая этот список, мы можем получить любой узел из кучи за время O(1), учитывая, что мы знаем исходный порядок, в котором узел был вставлен в кучу. Таким образом, если порядок узлов, в котором создаётся куча, совпадает с номером индекса узлов Graph, теперь у нас есть отображение узла Graph до относительного местоположения этого узла в MinHeap в постоянном времени! Чтобы иметь возможность поддерживать это отображение в актуальном состоянии за время O(1), все элементы, передаваемые в MinHeap как узлы, должны каким-то образом «знать» свой исходный индекс, а MinHeap необходимо знать, как считывать исходный индекс с этих узлов. Это требуется для того чтобы он мог обновить значение order_mapping по номеру индекса свойства индекса узла index до значения текущей позиции этого узла в списке узлов MinHeap. Поскольку нам нужно разрешить использование MinHeap, тем, кто не нуждается в этом отображении, А ТАКЖЕ нам нужно, чтобы любые типы данных были узлами кучи, мы можем снова разрешить добавление лямбда-выражения пользователем. Оно сообщит MinHeap, как получить номер индекса из любого типа данных, что добавляются в кучу — его названием будет get_index.

Например, если бы данные для каждого элемента в куче были списком структуры [data, index], лямбда get_index была бы: lambda el: el [1]. Кроме того, мы можем установить для get_index значение по умолчанию None, и доверить ему принятие решений, поддерживается или нет массив order_mapping. Таким образом, если пользователь не вводит лямбду, чтобы сообщить куче, как получить индекс из элемента, куча не будет отслеживать order_mapping, что позволяет пользователю использовать кучу без этой функциональности только с базовыми типами данных, такими как целые числа. Лямбда get_index, что будет в итоге использоваться, так как будет задействован пользовательский объект узла, будет очень простой: lambda node: node.index ().

Результатом совмещения решений 1 и 2 является одно чистое решение. Создается класс DijkstraNodeDecorator для декорирования всех узлов, составляющих граф. Этот декоратор предоставит дополнительные данные о provisional distance (инициализированном в бесконечность) и hoop list (инициализированном в пустой массив). Кроме того, он будет реализован с помощью метода, который позволит объекту обновляться самому. Потом это можно использовать в лямбда-выражении для decrease_key. DijkstraNodeDecorator сможет получить доступ к индексу декорируемого узла, и мы воспользуемся этим фактом, указав куче, как получить индекс узла при помощи лямбды get_index из Решения 2.

Финальный код алгоритма Дейкстры Python:

Использоваля для декорирования узлов в реализации Graph ниже.

MinHeap модифицирован с лямбдой, что позволяет любому типу данных использоваться в виде узла.

Результат вывода финального кода:

Как видите, вывод такой же, как и в прошлом варианте реализации алгоритма. Сам код выглядит теперь намного аккуратнее. Кроме того, сейчас нам удалось добиться реализации алгоритма Дейкстры за время O((n + e)lg(n)).