Свойство краевой релаксации для алгоритма Дейкстры и алгоритма Беллмана Форда

Опубликовано: 26 Февраля, 2023

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

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

Расслабление:

Свойство Edge Relaxation определяется как операция ослабления ребра u → v путем проверки того, является ли наиболее известный путь от S(source) к v переходом от S → v или через ребро u → v. Если это в последнем случае мы обновляем путь до этой минимальной стоимости.

Первоначально стоимость достижения от S до v устанавливается бесконечной (∞), а стоимость достижения от S до S равна нулю.

Представляя стоимость расслабленного ребра v математически,

d[v] = min{ d[v], d[u] + c(u, v) } 

И основной алгоритм релаксации будет таким:

if ( d[u] + c(u, v) < d[v] ) then

{
d[v] = d[u] + c(u, v)
}

где d[u] представляет стоимость достижения от S до u

d[v] представляет стоимость достижения от S до v
c(u, v) представляет стоимость достижения от u до v

Решение задачи о кратчайшем пути из одного источника методом релаксации краев

  • В задачах о кратчайших путях с одним источником нам нужно найти все кратчайшие пути из одной начальной вершины во все остальные вершины. Ослабляя ребро, мы проверяем, можем ли мы улучшить этот кратчайший путь (с помощью метода жадного подхода).
  • Это означает, что при обходе графа и поиске кратчайшего пути к конечному узлу мы обновляем стоимость путей, которые у нас есть для уже известных узлов, как только мы находим более короткий путь к нему.
  • Пример ниже прояснит и полностью объяснит работу свойства Relaxation.
  • На данном рисунке показан граф G, и мы должны найти минимальную стоимость достижения B из источника S.

Вход : график — G

Пусть A будет u , а B будет v.

Расстояние от источника до источника будет равно 0.
=> д[С] = 0

Также изначально расстояние между другими вершинами и S будет бесконечным.

ИНИЦИАЛИЗАЦИЯ – ПУТЬ С ОДНИМ ИСТОЧНИКОМ (G, S)

for each vertex v in the graph

d[v] = ∞
d[S] = 0

Теперь начинаем расслаблять А.

The shortest path from vertex S to vertex A is a single path ‘S → A’.

d[u] = ∞

Because, d[S] + c(S, u) < d[u]
d[u] = d[S] + c(S, u) = 0 + 20
=> d[u] = 20

Теперь расслабим вершину B.

The process remains the same the only difference we observe is that there are two paths leading to B. 

The path I: ‘S→B’
Path II: ‘S→A→B’

First, consider going through the path I – d[v] = ∞

Because, d[S] + c(S, v) < d[v]
d[v] = d[S] + c(S, v) = 0 + 40
=> d[v] = 40

Since its a lower value than the previous initialized d[v] is updated to 40, but we will now proceed to checking path II as per the greedy method approach.

d[v] = 40
Because, d[u] + c(u, v) < d[v]
d[v] = d[u] + c(u, v) = 20 + 10
=> d[v] = 30

Поскольку новое d[v] имеет меньшую стоимость, чем предыдущее в случае I, мы снова обновляем его до нового, полученного путем выбора пути II. Мы не можем обновить значение d ниже этого значения, поэтому завершаем релаксацию края.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ