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

Что оно делает?

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

Давайте построим график

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

Реализация графа

Перво-наперво. Граф - это набор узлов, соединенных ребрами:

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

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

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

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

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

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

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

Я могу использовать эти классы Node и Graph для описания нашего примера графа. Мы можем настроить наш график выше в коде и увидеть, что мы получили правильную матрицу смежности:

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

[0, 1, 1, 0, 1, 0]
[1, 0, 1, 1, 0, 0]
[1, 1, 0, 1, 0, 1]
[0, 1, 1, 0, 1, 0]
[1, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0]

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

Что выводит матрицу смежности:

[0 , 5 , 10, 0, 2, 0]
[5 , 0 , 2 , 4 , 0 , 0]
[10, 2, 0, 7, 0, 10]
[0 , 4 , 7 , 0 , 3 , 0]
[2 , 0 , 0 , 3 , 0 , 0]
[0, 0 , 10, 0 , 0 , 0]

И визуально наш график теперь будет выглядеть так:

Если бы я хотел, чтобы мои ребра содержали больше данных, я мог бы иметь матрицу смежности, содержащую граничные объекты, а не только целые числа.

Обзор алгоритма

Прежде чем мы перейдем непосредственно к коду, давайте коснемся некоторых базовых моментов.

Алгоритм Дейкстры изначально был разработан для поиска кратчайшего пути между двумя конкретными узлами. Однако сегодня он также широко используется для поиска кратчайших путей между исходным узлом и всеми другими узлами. Последнее я буду программировать сегодня. Чтобы выполнить первое, вам просто нужно остановить алгоритм, как только ваш целевой узел будет добавлен в ваш seen набор (это будет иметь больше смысла позже).
Установите provisional_distance всех узлов от исходного узла на бесконечность.

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

Продолжая логику, используя наш примерный график, я просто делаю то же самое из E, что и из A. Я обновляю всех E ближайших соседей с условными расстояниями, равными length(A to E) + edge_length(E to neighbor) ЕСЛИ это расстояние меньше текущего условного расстояния, или временное расстояние не было установлено. (Примечание: я просто инициализирую все временные расстояния до бесконечности, чтобы получить эту функциональность). Затем я жадно выбираю, какой узел следует оценить следующим, выбирая узел на всем графике с наименьшим условным расстоянием и добавляю E к моему набору seen nodes, чтобы не переоценивать его. Этот новый узел имеет ту же гарантию, что и E, что его условное расстояние от A является его определенным минимальным расстоянием от A. Чтобы понять это, давайте оценим возможности (хотя они могут не коррелировать с нашим примером графа, мы продолжим имена узлов для ясности ). Если следующий узел является соседом E, но не A, тогда он будет выбран, потому что его предварительное расстояние все еще короче, чем у любого другого прямого соседа A, поэтому нет другого возможного кратчайшего пути к нему, кроме E. Если следующий выбранный узел ЯВЛЯЕТСЯ прямым соседом A, то есть вероятность, что этот узел обеспечивает более короткий путь к некоторым из соседей E, чем сам E.

А теперь давайте сделаем наше описание немного более формальным и подробным.

С изображениями

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

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

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

4. Хотя у нас есть не seen все узлы (или, в случае оценки узла от источника к одному, пока у нас нет seen узла назначения):

5. Установите current_node на узел с наименьшим provisional_distance во всем графике. Обратите внимание, что для первой итерации это будет source_node, потому что мы установили его provisional_distance в 0.

6. Добавьте current_node в набор seen_nodes.

7. Обновите provisional_distance каждого из соседей current_node, указав (абсолютное) расстояние от current_node до source_node плюс длину ребра от current_node до этого соседа, ЕСЛИ это значение меньше текущего provisional_distance соседа. Если для этого соседа никогда не было задано временное расстояние, помните, что оно инициализировано до бесконечности и, следовательно, должно быть больше этой суммы. Если мы обновим provisional_distance, также обновим «прыжки», которые мы взяли, чтобы получить это расстояние, объединив прыжки current_node с исходным узлом с самим current_node.

8. Завершить пока.

Обратите внимание, что дальше мы могли бы посетить D или B. Я выберу посещение B.

Пришло время кодировать

Теперь наша программа завершается, и у нас есть кратчайшие расстояния и пути для каждого узла в нашем графе!

Давайте посмотрим, как это может выглядеть в Python (это будет метод экземпляра внутри нашего ранее закодированного класса Graph и будет использовать его другие методы и структуру):

Прохладный! Мы все?

Мы можем протестировать нашу картинку выше, используя этот метод:

Чтобы получить удобочитаемый вывод, мы сопоставляем объекты нашего узла с их data, что дает нам вывод:

Где каждый кортеж равен (total_distance, [hop_path]). Это соответствует нашему изображению выше!

[(0, [‘A’]), (5, [‘A’, ‘B’]), (7, [‘A’, ‘B’, ‘C’]), (5, [‘A’, ‘E’, ‘D’]), (2, [‘A’, ‘E’]), (17, [‘A’, ‘B’, ‘C’, ‘F’])]

Неа! Но почему? Мы можем сделать это быстрее! Если все, что вам нужно, это функциональность, на этом все готово!

Кучи

Для храбрых сердцем давайте сосредоточимся на одном конкретном шаге. На каждой итерации мы должны найти узел с наименьшим условным расстоянием, чтобы принять следующее жадное решение. Прямо сейчас мы ищем list, который мы вызвалиqueue (используя значения в dist), чтобы найти то, что нам нужно. Этот queue может иметь максимальную длину n, которая является нашим числом узлов. Следовательно, наша итерация по этому списку является операцией O (n), которую мы выполняем каждую итерацию нашего цикла while. Поскольку наш цикл while выполняется до тех пор, пока каждый узел не станет seen, теперь мы выполняем операцию O (n) n раз! Итак, наш алгоритм O (n²) !! Это нехорошо. Но это не все! Если вы посмотрите на реализацию матрицы смежности нашего Graph, вы заметите, что нам нужно просмотреть всю строку (размером n), чтобы найти наши связи! Это еще одна операция O (n) в нашем цикле while. Как это исправить? Ну, сначала мы можем использовать кучу, чтобы получить наше наименьшее предварительное расстояние за время O (lg (n)) вместо времени O (n) (с двоичной кучей - обратите внимание, что куча Фибоначчи может сделать это за O (1)) , а во-вторых, мы можем реализовать наш граф со списком смежности, где каждый узел имеет список подключенных узлов, вместо того, чтобы просматривать все узлы, чтобы увидеть, существует ли соединение. Это показывает, почему так важно понимать, как мы представляем структуры данных. Если бы мы реализовали кучу с представлением матрицы смежности, мы бы не изменили асимптотическое время выполнения нашего алгоритма с помощью кучи! (Примечание: если вы не знаете, что такое нотация с большим О, «почитайте об этом в моем блоге»!)

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

Основное условие: недопустимо отрицательная длина кромки.

Двоичная куча, формально, представляет собой полное двоичное дерево, которое поддерживает свойство кучи. Хорошо, звучит здорово, но что это значит?

Полное двоичное дерево. Это древовидная структура данных, в которой КАЖДЫЙ родительский узел имеет ровно два дочерних узла. Если дочерних узлов недостаточно, чтобы дать последней строке родительских узлов по 2 дочерних узла, дочерние узлы будут заполняться слева направо.

Как это выглядит?

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

Применяя этот принцип к нашему приведенному выше полному двоичному дереву, мы получим что-то вроде этого:

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

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

Итак, мы знаем, что двоичная куча - это особая реализация двоичного дерева, поэтому давайте начнем с программирования BinaryTreeclass, и мы сможем унаследовать нашу кучу от него. Чтобы реализовать двоичное дерево, наша основная структура данных будет массивом, и мы будем вычислять структуру дерева по индексам наших узлов внутри массива. Например, наше исходное двоичное дерево (первое изображение в разделе полное двоичное дерево) будет иметь базовый массив [5,7,18,2,9,13,4]. Мы определим отношения между узлами, оценив индексы узла в нашем базовом массиве. Поскольку мы знаем, что каждый родительский узел имеет ровно 2 дочерних узла, мы называем наш 0-й индекс корнем, а его левый дочерний элемент может быть индексом 1, а его правый дочерний элемент может быть индексом 2. В более общем случае, узел с индексом i будет иметь левый дочерний элемент в index 2*i + 1 и правый дочерний элемент по индексу 2*i + 2. Узел с индексомi будет иметь родителя с индексом floor((i-1) / 2).

Итак, наш BinaryTree класс может выглядеть примерно так:

Теперь мы можем получить MinHeap унаследовать от BinaryTree, чтобы уловить эту функциональность, и теперь наш BinaryTree можно повторно использовать в других контекстах!

Хорошо, почти готово! Теперь все, что нам нужно сделать, это определить возможности, которыми должен обладать наш MinHeap класс, и реализовать их! Нам нужна наша куча, чтобы иметь возможность:

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

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

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

FUNCTION min_heapify_subtree(i)
  index_of_min = i
  IF left_child exists AND left_child < node[index_of_min]
    index_of_min = left_child_index
  ENDIF
  IF right_child exists AND right_child < node[index_of_min]
    index_of_min = right_child_index
  ENDIF 
  IF index_of_min != i
    swap(nodes[i], nodes[index_of_min])
    min_heapify_subtree(index_of_min)
  ENDIF
END

Чтобы превратить полностью случайный массив в правильную кучу, нам просто нужно вызвать min_heapify_subtree на каждом узле, начиная с нижних листьев. Итак, мы можем сделать метод min_heapify:

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

FUNCTION min_heapify
  FOR index from last_index to first_index
    min_heapify_subtree(index)
  ENDFOR
END

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

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

FUNCTION pop
  min_node = nodes[0]
  IF heap_size > 1 
    nodes[0] = nodes[nodes.length - 1]
    nodes.pop() // remove the last element from our nodes array
    min_heapify_subtree(0)
  ELSE IF heap_size == 1
    nodes.pop()
  ELSE
    return NIL // the heap is empty, so return NIL value
  ENDIF
  return min_node
END

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

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

Хорошо, давайте посмотрим, как все это выглядит на Python!

FUNCTION decrease_key(index, value)
  nodes[index] = value
  parent_node_index = parent_index(index)
  WHILE index != 0 AND nodes[parent_node_index] > nodes[index]
    swap(nodes[i], nodes[parent_node_index])
    index = parent_node_index
    parent_node_index = parent_index(index)
  ENDWHILE
END

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

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

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

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

[ 
  [ NodeA, [(NodeB, 5), (NodeC, 10), (NodeE, 2)] ],
  [ NodeB, [(NodeA, 5), (NodeC, 2), (NodeD, 4)] ],
  [ NodeC, [(NodeA, 10), (NodeB, 2), (NodeD, 7), (NodeF, 10)] ],
  [ NodeD, [(NodeB, 4), (NodeC, 7), (NodeE, 3)] ],
  [ NodeE, [(NodeA, 2), (NodeD, 3)] ],
  [ NodeF, [(NodeC, 10)]
]

Затем давайте сосредоточимся на том, как мы реализуем нашу кучу для достижения лучшего алгоритма, чем наш текущий алгоритм O (n²). Если мы посмотрим назад на наш метод dijsktra в нашем классе «Матрица смежности createdGraph», мы увидим, что мы перебираем всю нашу очередь, чтобы найти минимальное 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) раз. Внутри этого внутреннего цикла нам нужно обновить наш provisional distance потенциально для каждого из этих подключенных узлов. Для этого будет использован метод decrease_key нашей кучи, который, как мы уже показали, равен O (lg (n)). Таким образом, наше общее время выполнения будет O ((n + e) lg (n)).

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

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

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

Вместо того, чтобы сохранять установленный параметр seen_nodes, мы определим, посетили ли мы узел или нет, в зависимости от того, остается он в нашей куче или нет. Помните, что когда мы выталкиваем () узел из нашей кучи, он удаляется из нашей кучи и, следовательно, по логике эквивалентен тому, что был «замечен».
Так что же значит быть жадным алгоритмом? Это означает, что мы принимаем решения, основываясь на самом лучшем на данный момент выборе. Это не всегда лучший вариант - например, если вы реализовываете шахматного бота, вы не захотите забрать ферзя другого игрока, если он откроет вам мат на следующий день. двигаться! Для подобных ситуаций лучше подойдет «минимакс». В нашем сегодняшнем случае этот жадный подход является лучшим решением, и он резко сокращает количество проверок, которые мне нужно выполнять без потери точности. Как?? Что ж, допустим, я на своем исходном узле. Я предполагаю, что начальное предварительное расстояние от исходного узла до каждого другого узла в графе составляет бесконечность (пока я не проверю их позже). Я знаю, что по умолчанию расстояние от исходного узла до исходного равно minium (0), поскольку не может быть отрицательной длины ребер. Мой исходный узел смотрит на всех своих соседей и обновляет их предварительное расстояние от исходного узла до длины ребра от исходного узла до этого конкретного соседа (плюс 0). Обратите внимание, что вы ДОЛЖНЫ проверять каждого ближайшего соседа; нет никакого способа обойти это. Затем мой алгоритм делает жадный выбор для следующей оценки узла, который имеет кратчайшее предварительное расстояние до исходного узла. Я помечаю свой исходный узел как visited, чтобы не возвращаться к нему, а перехожу к следующему узлу. Теперь давайте рассмотрим, где мы находимся с логической точки зрения, потому что это важное осознание. Узел, который я сейчас оцениваю (ближайший к исходному узлу), НИКОГДА не будет повторно оцениваться на предмет его кратчайшего пути от исходного узла. Его предварительное расстояние теперь превратилось в определенное расстояние. Хотя вполне могут быть пути от исходного узла к этому узлу другими путями, я уверен, что они будут иметь более высокую стоимость, чем текущий путь узла, потому что я выбрал этот узел , потому что это было кратчайшее расстояние от исходного узла, чем от любого другого узла, подключенного к исходному узлу. Таким образом, любой другой путь к этому режиму должен быть длиннее, чем текущее расстояние от источника до узла для этого узла. Используя наш пример графа, если мы установим наш исходный узел как A, мы установим временные расстояния для узлов B, C и E. Поскольку E находился на кратчайшем расстоянии от A, мы затем посетили узел E. Теперь, несмотря на то, что существует несколько других способов добраться от A до E, я знаю, что они имеют более высокий вес, чем мое текущее расстояние A → E, потому что эти другие маршруты должны проходить через B или C, что я подтвердил быть дальше от A, чем E от A. Был сделан мой жадный выбор, который ограничивает общее количество проверок, которые мне нужно выполнить, и я не теряю точности! Довольно круто.

3. Хотя размер нашей кучи составляет ›0: (выполняется n раз)

4. Установите current_node на возвращаемое значение heap.pop().

5. Для n в current_node.connections используйте heap.decrease_key, если это соединение все еще находится в куче (не было замечено) И если текущее значение provisional distance больше, чем предварительное расстояние current_node плюс вес края до этого соседа. Этот цикл for будет выполняться всего n + e раз, а его сложность составляет O (lg (n)).

6. Завершить пока.

Когда мы реализуем это, нам нужно решить две проблемы:

Проблема 1: мы запрограммировали нашу кучу на работу с массивом чисел, но нам нужно, чтобы узлы нашей кучи инкапсулировали provisional distance (метрику, к которой мы добавляем кучу), взятые переходы И узел, который расстояние соответствует.

Проблема 2: мы должны проверить, находится ли узел в нашей куче, И мы должны обновить его provisional distance с помощью метода decrease_key, который требует индекса этого узла в куче. Но наша куча постоянно меняет местами свои индексы, чтобы сохранить свойство кучи! Мы должны убедиться, что не решаем эту проблему, просто просматривая всю нашу кучу в поисках местоположения этого узла. Это будет операция O (n), выполненная (n + e) раз, что означает, что мы создали кучу и бесплатно переключились на реализацию списка смежности! Нам нужно сделать это за O (1) раз.

Решение 1. Мы хотим, чтобы наша реализация кучи была как можно более гибкой. Чтобы позволить ему принимать любой тип данных в качестве элементов в базовом массиве, мы можем просто принимать необязательные анонимные функции (например, лямбда-выражения) при создании экземпляра, которые предоставляются пользователем, чтобы указать, как он должен работать с элементами внутри массива, если эти элементы быть более сложным, чем просто число. Значением по умолчанию для этих лямбда-выражений могут быть функции, которые работают, если элементы массива являются просто числами. Итак, если требуется простая куча чисел, пользователю не нужно вставлять лямбды. Эти настроенные процедуры нам понадобятся для сравнения элементов, а также для возможности уменьшения значения элемента. Мы можем назвать наше сравнение лямбда is_less_than, и по умолчанию оно должно быть lambda: 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, который отображает исходный порядок вставленных узлов в их текущий порядок внутри массива nodes. Назовем этот список order_mapping. Поддерживая этот список, мы можем получить любой узел из нашей кучи за время O (1), при условии, что мы знаем исходный порядок, в котором узел был вставлен в кучу. Итак, если порядок узлов, с которыми я создаю свою кучу, совпадает с порядковым номером моих узлов Graph, теперь у меня есть отображение моего узла Graph на относительное расположение этого узла в моем MinHeap в постоянное время! Чтобы иметь возможность поддерживать это отображение в актуальном состоянии за время O (1), все элементы, переданные в MinHeap как nodes, должны каким-то образом «знать» свой исходный индекс, а моему MinHeap нужно знать, как читать этот исходный индекс из этих узлов . Это необходимо, чтобы он мог обновить значение order_mapping в индексном номере свойства index узла до значения текущей позиции этого узла в списке MinHeap node. Поскольку мы хотим разрешить кому-то использовать 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 (инициализированы до бесконечности) и hops list (инициализированы пустым массивом). Кроме того, он будет реализован с помощью метода, который позволит объекту обновляться, что мы можем прекрасно использовать в лямбде для decrease_key. DijkstraNodeDecorator сможет получить доступ к индексу узла, который он украшает, и мы воспользуемся этим фактом, когда сообщим куче, как получить индекс узла, используя get_index лямбда из Решения 2.

И, наконец, код:

Этот последний код при запуске выводит:

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

[(0, [‘a’]), (2, [‘a’, ‘e’]), (5, [‘a’, ‘e’, ‘d’]), (5, [‘a’, ‘b’]), (7, [‘a’, ‘b’, ‘c’]), (17, [‘a’, ‘b’, ‘c’, ‘f’])]

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