В этом посте я объясняю проблемы кратчайших путей с одним источником из задач кратчайших путей, в которых нам нужно найти все пути от одной начальной вершины ко всем остальным вершинам. Я определяю кратчайшие пути как наименьший взвешенный путь от начальной вершины до целевой вершины из всех других путей во взвешенном графе. Здесь вы можете думать, что «взвешенный» в взвешенном пути означает стоимость достижения целевой вершины (некоторой вершины). С этого момента, когда я говорю просто граф, это означает взвешенный граф.
На приведенном ниже графике давайте подумаем о кратчайших путях от начальной вершины S до других вершин A и B.
Кратчайший путь из вершины S в вершину A становится «S → A». В приведенном выше графике есть единственный путь из вершины S в вершину A, поэтому нам не нужно заботиться о весах. С другой стороны, мы можем найти два пути из вершины S в вершину B, которые являются «S → B» и «S → A → B», и кратчайший путь становится «S → A → B». В «S → B» вес пути равен 3, но в «S → A → B» вес пути становится равным 2, и он является самым коротким: 1 + 1 = 2. Мы можем рассматривать вес кратчайшего пути как кратчайшее расстояние от начальной вершины до одной вершины.
2. Что такое релаксация краев?
Здесь я объясню важное и часто используемое понятие релаксации краев для решения задачи о кратчайших путях. Как правило, вы можете решить все проблемы с кратчайшими путями, используя релаксацию ребер. Релаксация ребер - это операция по вычислению стоимости достижения вершины ниже. Более конкретно, операция будет выглядеть так:
For the edge from the vertex u to the vertex v, if d[u]+w(u,v)<d[v] is satisfied, update d[v] to d[u]+w(u,v)
Вершины u и v являются соседями в графе, а d [u] и d [v] - стоимость достижения вершин u и v соответственно. Кроме того, w (u, v) обозначает вес ребра от вершины u до вершины v. Подводя итог всему, что было до сих пор, мы можем сделать этот рисунок ниже.
Теперь мы знаем, что можем достичь вершины u из начальной вершины S через две вершины, и этот путь стоит d [u]. Кроме того, мы можем достичь вершины v от начальной вершины S через четыре вершины, и этот путь стоит d [v].
Здесь релаксация краев изменяет d [v] на d [u] + w (u, v), когда d [u] + w ( u, v) меньше d [v]. Другими словами, он обновляет текущую стоимость достижения вершины v (d [v]) до более низкой стоимости достижения ( d [u] + w (u, v)). Причина обновления стоимости заключается в том, что путь через вершину u может быть короче, поскольку стоимость достижения пути через вершину u будет ниже, чем стоимость текущий путь. Фактически, алгоритмы задачи поиска кратчайших путей решают проблему путем многократного использования релаксации ребер.
Я покажу на примере, что мы можем решить задачу о кратчайших путях, многократно используя релаксацию ребер. Найдем кратчайшие пути для того же графа, что и раньше, по релаксации ребер. Я беру начальную вершину S и применяю релаксацию ребер к графу, чтобы получить кратчайшие пути к вершинам A и B.
Чтобы применить релаксацию ребер, нам нужно знать стоимость достижения, но нет никакого способа узнать ее перед поиском, поэтому мы инициализируем затраты на достижение для вершин A и B как бесконечность (∞). Бесконечная стоимость вершины означает, что мы не можем достичь этой вершины. С другой стороны, стоимость достижения от начальной вершины до начальной вершины равна нулю, поэтому мы устанавливаем значение d вершины S равным 0.
Сначала мы выбираем и расслабляем ребра, выходящие из вершины S, затем ребро, выходящее из вершины A. Прежде всего, мы применяем релаксацию ребер к ребру SA.
Ребро SA удовлетворяет d [S] + w (S, A) ‹d [A], мы устанавливаем d [A] как d [S] + w (S, A) = 1. Здесь Π [A] обозначает вершину, которая идет перед вершиной A на пути достижения cost d [A]. В этом случае Π [A] равно S. Π [A] = S означает, что путь достижения затрат d [A] всегда использует вспомогательный путь, A ← S. Детали будут описаны ниже, но мы можем восстановить путь, используя Π.
Таким же образом расслабляем край SB.
Ребро SB удовлетворяет условию d [S] + w (S, B) ‹d [B], поэтому мы устанавливаем d [B] как d [S] + w (S, B) = 3. Для реконструкции пути d [B] мы полагаем Π [B] как S. Затем мы ослабляем ребро AB, выходящее из вершины A.
Ребро AB удовлетворяет условию d [A] + w (A, B) ‹d [B], поэтому мы устанавливаем d [B] как d [A] + w (A, B) = 2. После обновления значения d для B мы также обновляем Π [B] как A. Из рисунка выше видно, что кратчайшие расстояния от вершины S до вершин A и B равны стоимость достижения d. Мы не можем обновить значение d ниже, поэтому завершаем релаксацию краев.
Здесь, давайте подтвердим, что мы можем восстановить кратчайший путь, используя Π [A] = S и Π [B] = A. В приведенном выше графике мы собираемся восстановить кратчайший путь из вершины S в вершину B в качестве примера. Из Π [B] = A мы можем знать, что мы должны посетить вершину A, прежде чем достигнем вершины B на пути к вершине B. Из [A] = S мы можем знать, что мы должны сначала посетить вершину S, а затем достичь вершины A. Вершина S - это начальная вершина, поэтому мы больше не можем двигаться назад. Переворачивая вершины, которые мы получили до сих пор, мы можем получить кратчайший путь из вершины S в вершину B, «S → A → B». Как правило, мы можем восстановить кратчайший путь для вершины v путем обратного отслеживания Π [v], Π [Π [v]], Π [Π [Π [v]]],… и переворачивая полученные вершины.
3. Порядок релаксации.
В предыдущем разделе нас не заботит порядок ослабления краев, но как нам определить порядок? Или нам это действительно важно? Кажется, что мы можем получить кратчайший путь, произвольно расслабляя ребра. Однако это неверно. Здесь я объясню, почему мы должны заботиться о порядке и как выбрать край, чтобы расслабиться.
По правде говоря, действительно плохой случай с эффективностью вычислений будет, если вы выберете и ослабите край случайным образом. Например, давайте представим следующий график. Я предполагаю, что значения d на этом графике уже инициализированы.
Сначала расслабим края прямой линии слева направо.
Далее расслабляем край EG.
Затем расслабляем край CE.
Здесь вы можете обнаружить, что мы снова можем расслабить крайнюю EG.
Кроме того, когда мы расслабляем ребро AC, мы можем снова ослабить ребра CE и EG. Поэтому, если мы не обращаем внимания на порядок, мы будем ослаблять одно и то же лезвие снова и снова. В приведенном выше примере мы можем эффективно ослабить края, если ослабим их слева направо. Однако есть слишком плотные графики для визуализации, как в примере выше. Так что заранее найти эффективный заказ нереально. Вот почему мы должны заботиться о расслабляющем порядке.
Ну а как выбрать и расслабить края. Фактически, алгоритмы кратчайших путей, такие как алгоритм Дейкстры или алгоритм Беллмана-Форда, дают нам расслабляющий порядок. Что это означает, что каждый алгоритм кратчайших путей в основном повторяет релаксацию ребер и выстраивает порядок ослабления в зависимости от природы графа (положительные или отрицательные веса, DAG,… и т. Д.). Другими словами, мы должны искать способ выбора и ослабления ребер, наблюдая за природой графа. Таким образом, каждый алгоритм кратчайших путей имеет следующую общую структуру:
1. Initialize d and Π in the graph 2. Choose the edge somehow (it depends on the algorithm) and Relax it.
4. Кратчайший путь по DAG и его реализация
В предыдущем разделе я сказал, что мы должны выбрать способ релаксации ребер, наблюдая за природой графа. Здесь я объясню простой и легкий алгоритм кратчайших путей для DAG (Направленный ациклический граф) с реализацией Python. DAG - это граф, не имеющий цикличности. В этом разделе я объясню алгоритм, как вы знаете топологический порядок. Если вы не знакомы с этим, посмотрите мою статью Понимание поиска в глубину и топологической сортировки с помощью Python?
В алгоритме кратчайших путей на DAG мы можем получить кратчайшие пути, выбирая и ослабляя отходящие ребра в топологическом порядке. Вот конкретный алгоритм:
1. Initialize the d value of the starting vertex as 0 and the other vertices as ∞ 2. Relax the out-going edges in topological order
Посмотрим, как работает алгоритм. Я показываю граф, который я инициализировал d и топологически отсортировал следующим образом. Я предполагаю, что начальная вершина - B. Попробуем решить задачу о кратчайших путях.
Каждая вершина топологически отсортирована, поэтому мы просто ослабляем отходящие ребра слева направо. Мы не можем ослабить выходящее ребро из самой левой вершины A, поэтому мы не обновляем d.
Затем мы расслабляем выходящие из вершины B ребра, которыми являются BC и BD. После того, как мы ослабим края, мы обновим Π. Положим Π [C] как B и Π [D] как B.
Затем мы ослабляем отходящие ребра от вершины C. Мы не можем ослабить отходящие ребра до вершины D, поэтому мы обновляем только d [E] и d [F]. Кроме того, мы обновляем Π [E] как C, Π [F] как C.
Мы обновляем исходящее ребро из вершины D. Мы обновляем только d [E] и Π [E] как D.
Обновляем выходящее ребро из вершины E. Мы также обновляем Π [F] как E.
Из вершины F нет отходящего ребра. Завершаем релаксацию ребер. Наконец, мы получаем кратчайшие расстояния следующим образом: мы не проверяем, работает ли это здесь, но мы можем восстановить кратчайшие пути из Π.
Затем давайте реализуем алгоритм кратчайших путей на DAG в Python для лучшего понимания. Реализация приведена ниже: В этой реализации этот код решает проблему кратчайших путей на графе, используемом в приведенном выше объяснении. Этот код оценивает d и Π для решения проблемы. Я предполагаю, что мы уже заранее знали топологический порядок.
Во-первых, давайте посмотрим, как выражаются график и его веса. В приведенном выше коде график реализован следующим образом:
graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D', 'E', 'F'],
'D': ['E', 'F'],
'E': ['F'],
'F': []}
weights = {('A', 'B'): 5, ('A', 'C'): 2,
('B', 'C'): 2, ('B', 'D'): 6,
('C', 'D'): 7, ('C', 'E'): 4, ('C', 'F'): 2,
('D', 'E'): -1, ('D', 'F'): 1,
('E', 'F'): -2}
Соответствующий рисунок для графика ниже:
Например, когда мы смотрим на вершину C, graph ['C'] возвращает ['D', 'E', 'F'], которые являются достижимыми соседями из вершины C. Итак, эти вершины образуют выходящие ребра из вершины C. Кроме того, вы обнаружите, что weights [u, v] соответствует весу край УФ.
Затем давайте посмотрим на роль каждой строки dag_shortest_path, чтобы получить кратчайшие пути. Строки со 2 по 4 представляют собой следующую инициализацию: установите d начальной вершины как 0, а остальные вершины как ∞. Кроме того, эти строки инициализируют Π для восстановления пути.
d = {v: INF for v in graph}
d[s] = 0
pi = {s: None}
Линии с 9 по 12 соответствуют краевой релаксации. d_temp ‹d [v] в коде соответствует d [u ] + w (u, v) ‹d [v] в условие краевой релаксации. Когда это условие выполнено, обновляется d [v]. После обновления d он также обновляет Π.
d_temp = d[u] + weights[u, v] if d_temp < d[v]: d[v] = d_temp pi[v] = u
Код повторяет этот процесс для выходящих ребер из каждой вершины в топологическом порядке. Этот повторяющийся процесс выполняется двумя циклами for. torder удерживает вершины в топологическом порядке. Кроме того, граф возвращает вершины для построения исходящих ребер из вершины. Итак, мы получаем ребро uv, рассматривая вершину из torder как u и graph [ u] как v.
for u in torder:
for v in graph[u]:
# relax(u, v)
На этом все пояснения по коду. Мы не проверяем результат, но вы можете выполнить код с помощью следующей команды в своем терминале: Вы обнаружите, что можете правильно получить d и Π.
curl -s https://gist.githubusercontent.com/yasufumy/e6477c836baa85735f6019bc0b0c1460/raw/ee4885e5d21f009ee490038525887d8fcf80f8d8/dag_shortest_path.py | python3
Наконец, давайте подумаем о временной сложности этого алгоритма. В этом алгоритме есть две основные вычислительные части. Один для топологической сортировки. Другой - для релаксации краев. В приведенном выше коде мы не выполняем топологическую сортировку, но на самом деле нам это нужно. Так что мы должны это учитывать. Мы можем выполнить топологическую сортировку с помощью поиска в глубину, поэтому временная сложность составляет O (| V | + | E |). Количество циклов влияет только на временную сложность релаксации края, потому что процессы в цикле выполняются в постоянное время. Количество петель для torder равно | V | а количество циклов для графика [u] равно | E |. Таким образом, временная сложность релаксации края составляет O (| V | + | E |). Таким образом, общая временная сложность алгоритма составляет O (| V | + | E |).
В этом посте я сосредоточусь на релаксации краев и объясню задачу кратчайших путей и ее алгоритм. Когда вы понимаете релаксацию краев, вы можете легко понять алгоритм Дийсктры или алгоритм Беллмана-Форда. Кроме того, вы можете узнать разницу между этими алгоритмами. Спасибо, что прочитали мою статью.
