Автор статьи: Рустем Галиев

IBM Senior DevOps Engineer & Integration Architect. Официальный DevOps ментор и коуч в IBM

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

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

Мы начнем с обзора базовых понятий, связанных с взвешенными графами и кратчайшими путями. Затем рассмотрим несколько ключевых алгоритмов, включая алгоритм Дейкстры и алгоритм Беллмана-Форда, предоставив читателю полное представление о том, как они работают и в каких ситуациях применяются.

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

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

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

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

• Оптимизация маршрутов и логистика. Применяется в логистике и транспортировке для оптимизации путей доставки и распределения ресурсов, таких как товары и грузы.

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

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

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

• Анализ путей в сети. Исследование путей и потоков в сетях, таких как транспортные системы и сети передачи данных.

• Биоинформатика. В анализе генетических сетей и взаимодействия белков.

• Финансовый анализ. В оценке рисков, анализе портфеля и предсказании финансовых рынков.

• Игровая индустрия. В создании игровых миров для реализации искусственного интеллекта и планирования действий персонажей.

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

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

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

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

На изображении выше путь C – E – A является кратчайшим путем с точки зрения общего количества ребер от C до A. Обратите внимание, что сумма весов ребер на этом пути равна 1 + 4 = 5. Однако Сумма пути C – B – D – A равна 2 + 1 + 1 = 4. На этом графике ни один другой путь из C в A не имеет меньшей суммы. Поскольку граф визуализируется очень тщательно, без каких-либо перекрывающихся ребер, это было просто. Для более сложных графов, чтобы не приходилось проверять множество потенциальных путей в поисках кратчайшего, вам понадобится алгоритм.

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

Вы должны быть в состоянии определить, что кратчайший путь по общим весам ребер от узла C к узлу A — это C-B-D-A с суммой 4. Но как бы вы разработали алгоритм для вычисления того же результата?

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

Начиная с узла C, есть два смежных ребра: C - B с весом ребра 2 и C - E с весом ребра 1. Поскольку цель состоит в том, чтобы минимизировать сумму, жадный алгоритм будет продвигаться вперед, выбирая ребро с наименьшим весом, или C - E. Давайте попробуем продолжить с узла E, у которого есть три ребра, но вы пришли из C, поэтому учитывайте только ребра, ведущие к D и A: ребро с наименьшим весом ведет к узлу D. Из этого узла идут два ребра с одинаковым весом: D — B и D — A. Какое из них взять? Как сделать так, чтобы вам не пришлось бесконечно кружить вокруг, пытаясь добраться от источника к цели?

При поиске в ширину и в глубину узлы помечались как посещенные, чего было достаточно, чтобы избежать многократного посещения узлов во время поиска. Этот подход здесь не сработает, поскольку возможно, что другая последовательность ребер от источника к целевому узлу, может в сумме дать меньшее значение, чем уже найденный результат. Например, путь C–E–D имеет общий суммарный вес ребра 4, но существует более короткий путь через C–B–D с суммарным весом ребра 3.

Давайте начнем с определения того, что именно должен вычислять алгоритм кратчайшего пути с одним источником. Учитывая назначенный исходный узел в графе G, цель состоит в том, чтобы вычислить dist_to[n] или кратчайший общий путь по весам ребер от источника до n. Если n недостижимо, то dist_to[n] = INFINITY. Естественно, кратчайший путь от назначенного исходного узла до самого себя равен нулю. Кроме того, вы хотели бы иметь возможность определить фактический путь с наименьшим общим весом ребер. Чтобы сделать это возможным, алгоритм должен также вычислить Edge_to[n] или предыдущее ребро на кратчайшем пути от источника до n. Эта структура аналогична структуре node_from[], вычисляемой во время поиска в ширину и в глубину.

Ниже приведен исходный граф вместе с полученным значением dist_to[n] от источника до каждого другого узла в графе, а также вычисленным значением Edge_to[n] для каждого узла. Эти структуры содержат информацию, необходимую для восстановления кратчайшего пути от источника до каждого достижимого узла графа. Действительно, чтобы восстановить кратчайший путь, общее расстояние которого равно 4, от источника до узла A, вы должны начать с целевого узла. Edge_to[A] сообщает вам, что последнее ребро на кратчайшем пути от C до A пришло из узла D. Затем, если вы посмотрите на Edge_to[D], то увидите, что последнее ребро на кратчайшем пути от C до D пришло из узла B. Наконец, Edge_to[B] содержит ребро от источника до B.

Алгоритм кратчайшего пути с одним источником должен вычислить вышеуказанную информацию для графа G.

Чтобы получить некоторое представление о том, как вычисляются эти значения, предположим, вы начинаете с ребер, прилегающих к узлу C, и вычисляете dist_to[] следующим образом, учитывая ребра к B и E. Также вычислите Edge_to[B] = C - B, а Edge_to[E] = C - E.

Имея эту информацию, каков кратчайший путь от C до D? Поскольку dist_to[D] неизвестен, вы можете использовать ребро E–D, чтобы создать путь C–E–D, общая длина которого равна 4, поэтому обновите dist_to[] соответствующим образом. Кроме того, вам следует записать Edge_to[D] = E - D, чтобы при необходимости вы могли восстановить этот путь позже.

Но теперь, когда вы рассматриваете ребро B - D, вы понимаете, что существует более короткий путь от C до D общего размера 3, если путь проходит через B. Чтобы записать эту информацию, измените dist[D] на 3 и убедитесь и запишите, что Edge_to[D] = B - D.

Основная идея алгоритма Дейкстры состоит в том, чтобы найти ребро, которое находит более короткий путь к узлу n, чей dist_to[n] равен либо БЕСКОНЕЧНОСТИ (поскольку это первый раз, когда он исследуется), либо чей dist_to[n] больше чем только что обнаруженный новый, более короткий путь. Эта концепция известна как расслабление края, которая представлена ниже в виде небольшого графика с тремя ребрами.

Если вы ищете кратчайший путь от A до других узлов, начните с вычисления dist[B] = 6 и dist[C] = 10 из-за существующих ребер. Однако вы можете ослабить ребро B–C, поскольку dist[B] + 2 < dist[C]. Через это ребро обнаруживается меньший кратчайший путь из А в С.

Ниже показана эта логика в коде:

def relax(e):
  u, v, weight = e[0], e[1], e[2]['weight']
  if dist_to[u] + weight < dist_to[v]:
    dist_to[v] = dist_to[u] + weight
    edge_to[v] = e

Я строю графы, используя NetworkX API. Взвешенное ребро в графе представлено в виде кортежа (u, v, Properties), где Properties — это словарь свойств ребра, включая его вес. Таким образом, чтобы получить вес ребра, используйте выражение e[2]['weight'].

Выше, если кратчайший путь от источника до узла u плюс вес ребра (u, v) меньше текущего кратчайшего пути от источника до v, то вы можете сохранить в dist[v] улучшенную длину кратчайшего пути, но также нужно записать, что ребро e является последним ребром на кратчайшем пути от источника до v.

Итак, теперь у нас есть рабочая стратегия: инициализировать dist_to[] значением INFINITY для всех узлов в G, за исключением того, что dist_to[source] = 0. Затем найдите ребра, которые можно ослабить, чтобы найти лучший, более короткий путь. Алгоритм Дейкстры показывает, как это сделать правильно и эффективно.

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

Используя небольшой граф G ниже, S изначально содержит только исходный узел:

Структура dist_to[] под графом содержит текущие вычисленные лучшие пути от C до любого другого доступного узла. В настоящее время вы даже не знаете, что другие узлы доступны, поэтому их значение dist_to равно INFINITY; только dist_to[C] равен 0.

Начиная с C, есть два ребра, которые могут ослабить значения dist_to. В частности, ребро C–E уменьшает dist_to[E] до 1, а ребро C–B уменьшает dist_to[B] до 2. Этот шаг релаксации влияет на два узла и их соответствующие значения dist_to и Edge_to (выделены желтым цветом выше).

Теперь расширьте S, найдя активный узел в dist_to, имеющий наименьшее значение. Эти активные узлы не принадлежат множеству S, а отражают горизонт поиска. Как вы можете видеть, узел E в настоящее время имеет наименьшее расстояние среди активных узлов, поэтому добавьте этот узел к S и ослабьте его на основе ребер, соседних с E, что влияет на dist_to[A] и dist_to[D]. Посмотрите, как значение dist_to[A] = 5 по пути C — E — A, а значение dist_to[D] = 4 по пути C — E — D.

Все узлы, выделенные черным цветом (то есть C и E), представляют узлы в S. Среди других активных узлов тот, чье значение dist_to наименьшее, — это узел B. Добавьте узел B к S:

Ослабляя ребро, примыкающее к B, а именно B - D, вы обнаруживаете, что расстояние до узла D уменьшается до 3, когда путь к D исходит из узла B. Теперь расширьте S, найдя активный узел, имеющий наименьшее значение. Это узел D, поэтому добавьте этот узел к S:

Расслабьте ребра, прилегающие к D, что уменьшит общее расстояние до A до 4, и запишите в Edge_to[A], что путь наименьшей общей длины приходит к A из D.

Единственным оставшимся активным узлом является узел A, и, поскольку он не обнаруживает дополнительных узлов, алгоритм завершается со следующими результатами:

Этот небольшой пример показывает, что нужно сделать. Ключевым вычислительным шагом выше является расширение S путем поиска активного узла в dist_to с наименьшим значением. Это, безусловно, кажется прекрасной возможностью использовать минимальную двоичную кучу для упорядочивания информации таким образом, чтобы можно было получить минимальное значение (и обновить кучу) с производительностью времени выполнения O(log N).

Однако существует проблема, которая возникает, когда вновь обнаруженный путь находит более короткий путь к узлу n, у которого уже есть вычисленное значение dist_to[n]. Одно дело обновить запись в dist_to[n] новым значением. Это еще одна попытка найти n в минимальной двоичной куче, чтобы можно было уменьшить его приоритет. К счастью, можно реализовать индексированную очередь с минимальным приоритетом, которая обеспечивает эту возможность, не теряя при этом эффективности минимальной двоичной кучи.

Начнем с демонстрации реализации алгоритма Дейкстры.

from indexed_pq import IndexedMinPQ

def dijkstra_sp(G, src):
  N = G.number_of_nodes()

  inf = float('inf')
  dist_to = {v:inf for v in G.nodes()}
  dist_to[src] = 0

Он начинается, как описано выше, с определения dist_to[n] как INFINITY для всех узлов в G, кроме назначенного исходного узла src, чье dist[src] = 0.

impq = IndexedMinPQ(N)
  impq.enqueue(src, dist_to[src])
  for v in G.nodes():
    if v != src:
      impq.enqueue(v, inf)

Алгоритм Дейкстры создает IndexedMinPQ с местом для N значений, помещая в очередь каждый узел (кроме источника, src) с приоритетом INFINITY. По мере обработки алгоритма Дейкстры узлы будут выводиться из очереди imq по одному, каждый из которых представляет следующий узел, добавляемый в набор S, описанный ранее.

Описанная ранее операция релаксации ключа реализована ниже с одним дополнительным шагом, необходимым для алгоритма Дейкстры. При необходимости Relax(e) обновляет dist_to[v] и Edge_to[v]:

  def relax(e):
    u, v, weight = e[0], e[1], e[2]['weight']
    if dist_to[u] + weight < dist_to[v]:
      dist_to[v] = dist_to[u] + weight
      edge_to[v] = e
      impq.decrease_priority(v, dist_to[v])

Когда будет найден новый кратчайший путь к v, возможно, потребуется изменить местоположение v в imq, чтобы переместить его ближе к началу приоритетной очереди. Эта операция была бы дорогостоящей в обычной минимальной двоичной куче, но IndexedMinPQ предлагает такую возможность с производительностью времени выполнения O(log N). Всякий раз, когда ребро ослабляется, соответствующий узел v корректно обновляется в imq.

 edge_to = {}
  while not impq.is_empty():
    n = impq.dequeue()
    for e in G.edges(n, data=True):
      relax(e)

  return (dist_to, edge_to)

Центральный цикл while обманчиво прост. Он удаляет из очереди узел n, имеющий кратчайший путь для тех узлов, которые не входят в набор S. Для всех соседних ребер, полученных с помощью G.edges(n, data=True), алгоритм проверяет, можно ли ослабить ребро.Если это возможно, то найден новый кратчайший путь, и impq корректируется в Relax(), чтобы цикл while извлекал правильный узел для следующей обработки.

def edges_path_to(edge_to, src, target):
  if not target in edge_to:
    raise ValueError('{} is unreachable from {}'.format(target, src))

  path = []
  v = target
  while v != src:
    path.append(v)
    v = edge_to[v][0]

  # last one to push is the source, which makes it
  # the first one to be retrieved
  path.append(src)
  path.reverse()
  return path

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

python -i shortest_sp.py 
import networkx as nx
G = nx.Graph()
G.add_edge('C', 'B', weight=2)
G.add_edge('C', 'E', weight=1)
G.add_edge('B', 'D', weight=1)
G.add_edge('E', 'D', weight=3)
G.add_edge('D', 'A', weight=1)
G.add_edge('E', 'A', weight=4)
(dist_to, edge_to) = dijkstra_sp(G, 'C')
print(dist_to['A'],'is equal to 4')
print(edges_path_to(edge_to, 'C', 'A'))
quit()

Приведенный выше код показывает, что кратчайший путь от C до A действительно есть C – B – D – A.

Теперь посмотрим, как реализован IndexedMinPQ.

Класс IndexedMinPQ имеет начальную структуру минимальной двоичной кучи.

class IndexedMinPQ:
  def __init__(self, size):
    self.N = 0
    self.size = size
    self.values = [None] * (size+1)
    self.priorities = [None] * (size+1) 
    # TBA: INIT

  def is_empty(self):
    return self.N == 0

  def swim(self,child):
    while child > 1 and self.less(child//2, child):
      self.swap(child, child//2)
      child = child//2

  def sink(self, parent):
    while 2*parent <= self.N:
      child = 2*parent
      if child < self.N and self.less(child, child+1):
        child += 1
      if not self.less(parent, child):
        break
      self.swap(child, parent)

      parent = child

  def enqueue(self, v, p):
    self.N += 1
    self.values[self.N], self.priorities[self.N] = v, p
    # TBA: ENQUEUE

    self.swim(self.N)

  def less(self, i, j):
    return self.priorities[i] > self.priorities[j]

  def swap(self, i, j):
    self.values[i],self.values[j] = 
      self.values[j],self.values[i]
    self.priorities[i],self.priorities[j] = 
      self.priorities[j],self.priorities[i]
    # TBA: SWAP

  def dequeue(self):
    min_value = self.values[1]
    self.values[1] = self.values[self.N]
    self.priorities[1] = self.priorities[self.N]
    # TBA: DEQUEUE

    self.values[self.N] = self.priorities[self.N] = None

    self.N -= 1
    self.sink(1)
    return min_value

Вы можете сказать, что это минимальная двоичная куча, потому что вспомогательная функция less(i, j) смотрит назад, но она просто отражает наблюдение, что когда числовой приоритет для элемента i больше, чем числовой приоритет для элемента j, то есть когда родительский узел должен быть заменен своим дочерним узлом.

IndexedMinPQ может уменьшить приоритет для данного значения только в том случае, если он может найти это значение в минимальной двоичной куче. Для этого требуется дополнительное хранилище. Это делается путем создания словаря location в методе __init__(), который отображает местоположение индекса для каждого значения в двоичной куче.

self.location = {}

Всякий раз, когда значение v помещается в очередь (v, p), словарь местоположений записывает, что v помещается в индексную позицию N, то есть следующую доступную ячейку в минимальной двоичной куче.

self.location[v] = self.N

После того, как значение помещено в очередь(), оно должно плавать() в нужное место, поэтому важно, чтобы каждый раз, когда swap(i, j) меняет местами два значения в минимальной двоичной куче, соответствующие местоположения для i и j также должны быть обновлены. :

self.location[self.values[i]] = i
self.location[self.values[j]] = j

И, наконец, всякий раз, когда dequeue() удаляет минимальное значение, значение в конце минимальной двоичной кучи заменяется на позицию с индексом 1. dequeue() должна обновить местоположение значения в индексе 1, и это также выполняет некоторую очистку, удаляя старое местоположение для min_value, которое теперь удаляется из кучи, прежде чем sink() переместит это значение в правильное место.

self.location[self.values[1]] = 1
    self.location.pop(min_value)   # remove from dictionary

Если вам интересно, каждое значение, помещенное в очередь в IndexedMinPQ, уникально, поскольку оно представляет метку узла графа G, поэтому его можно использовать в качестве ключа в словаре местоположений.

Последний метод, который нужно добавить, — это важнейший метод уменьшения приоритета decrease_priority().

def decrease_priority(self, v, lower_priority):
    if not v in self.location:
      raise ValueError('Value does not exist.')
    idx = self.location[v]
    if lower_priority >= self.priorities[idx]:
      raise RuntimeError('Cannot increase priority'))

    self.priorities[idx] = lower_priority
    self.swim(idx)

Эта функция должна проверить, что (a) желаемое значение v действительно находится в IndexedMinPQ; и (b) новый приоритет для связывания на самом деле ниже, поскольку в противном случае запрос уничтожит свойство упорядоченной кучи для минимальной двоичной кучи.

Поскольку приоритет мог только уменьшиться, свойство упорядоченности кучи восстанавливается путем вызова метода swim() для индексного местоположения v в минимальной двоичной куче.

Поскольку все ключевые операции в IndexedMinPQ остаются O(log N), это не влияет на производительность во время выполнения, и его можно продолжать использовать в алгоритме Дейкстры, чтобы гарантировать, что его общая производительность во время выполнения в худшем случае составит O(N log N).

В итоге у нас получилось 3 файла:

IndexedMinPQ.py

class IndexedMinPQ:
  def __init__(self, size):
    self.N = 0
    self.size = size
    self.values = [None] * (size+1)
    self.priorities = [None] * (size+1) 
    self.location = {}

  def is_empty(self):
    return self.N == 0

  def swim(self,child):
    while child > 1 and self.less(child//2, child):
      self.swap(child, child//2)
      child = child//2

  def sink(self, parent):
    while 2*parent <= self.N:
      child = 2*parent
      if child < self.N and self.less(child, child+1):
        child += 1
      if not self.less(parent, child):
        break
      self.swap(child, parent)

      parent = child

  def enqueue(self, v, p):
    self.N += 1
    self.values[self.N], self.priorities[self.N] = v, p
    self.location[v] = self.N

    self.swim(self.N)

  def less(self, i, j):
    return self.priorities[i] > self.priorities[j]

  def swap(self, i, j):
    self.values[i],self.values[j] = 
      self.values[j],self.values[i]
    self.priorities[i],self.priorities[j] = 
      self.priorities[j],self.priorities[i]
    # TBA: SWAP

  def dequeue(self):
    min_value = self.values[1]
    self.values[1] = self.values[self.N]
    self.priorities[1] = self.priorities[self.N]
    self.location[self.values[1]] = 1
    self.location.pop(min_value)   # remove from dictionary


    self.values[self.N] = self.priorities[self.N] = None

    self.N -= 1
    self.sink(1)
    return min_value

  def decrease_priority(self, v, lower_priority):
    if not v in self.location:
      raise ValueError('Value does not exist.')
    idx = self.location[v]
    if lower_priority >= self.priorities[idx]:
      raise RuntimeError('Cannot increase priority'))

    self.priorities[idx] = lower_priority
    self.swim(idx)

shortest_sp.py

from indexed_pq import IndexedMinPQ

def dijkstra_sp(G, src):
  N = G.number_of_nodes()

  inf = float('inf')
  dist_to = {v:inf for v in G.nodes()}
  dist_to[src] = 0

  impq = IndexedMinPQ(N)
  impq.enqueue(src, dist_to[src])
  for v in G.nodes():
    if v != src:
      impq.enqueue(v, inf)

  def relax(e):
    u, v, weight = e[0], e[1], e[2]['weight']
    if dist_to[u] + weight < dist_to[v]:
      dist_to[v] = dist_to[u] + weight
      edge_to[v] = e
      impq.decrease_priority(v, dist_to[v])

  edge_to = {}
  while not impq.is_empty():
    n = impq.dequeue()
    for e in G.edges(n, data=True):
      relax(e)

  return (dist_to, edge_to)

def edges_path_to(edge_to, src, target):
  if not target in edge_to:
    raise ValueError('{} is unreachable from {}'.format(target, src))

  path = []
  v = target
  while v != src:
    path.append(v)
    v = edge_to[v][0]

  # last one to push is the source, which makes it
  # the first one to be retrieved
  path.append(src)
  path.reverse()
  return path

indexed_pq.py

class IndexedMinPQ:
  def __init__(self, size):
    self.N = 0
    self.size = size
    self.values = [None] * (size+1)
    self.priorities = [None] * (size+1)   # binary heap using 1-based indexing
    self.location = {}                    # For each value, remember its location in storage

  def is_empty(self):
    return self.N == 0

  def swim(self,child):
    while child > 1 and self.less(child//2, child):
      self.swap(child, child//2)
      child = child//2

  def sink(self, parent):
    while 2*parent <= self.N:
      child = 2*parent
      if child < self.N and self.less(child, child+1):
        child += 1
      if not self.less(parent, child):
        break
      self.swap(child, parent)

      parent = child

  def enqueue(self, v, p):
    self.N += 1
    self.values[self.N], self.priorities[self.N] = v, p
    self.location[v] = self.N             # record where it is being stored
    self.swim(self.N)

  def decrease_priority(self, v, lower_priority):
    if not v in self.location:
      raise ValueError('{} not in the indexed min priority queue.'.format(v))
    idx = self.location[v]
    if lower_priority >= self.priorities[idx]:
      raise RuntimeError('Value {} has existing priority of {} which is already lower than {}'.format(v, self.priorities[idx], lower_priority))

    self.priorities[idx] = lower_priority
    self.swim(idx)

  def less(self, i, j):
    return self.priorities[i] > self.priorities[j]

  def swap(self, i, j):
    self.values[i],self.values[j] = self.values[j],self.values[i]
    self.priorities[i],self.priorities[j] = self.priorities[j],self.priorities[i]

    self.location[self.values[i]] = i
    self.location[self.values[j]] = j

  def dequeue(self):
    min_value = self.values[1]
    self.values[1] = self.values[self.N]
    self.priorities[1] = self.priorities[self.N]
    self.location[self.values[1]] = 1

    self.values[self.N] = self.priorities[self.N] = None
    self.location.pop(min_value)   # remove from dictionary

    self.N -= 1
    self.sink(1)
    return min_value

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

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

• Узнать подробнее о вебинаре