algorithm
Алгоритм Беллмана-Форда

замечания

Алгоритм наименьшего пути одиночного источника (учитывая, что на графике есть отрицательный цикл)

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

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

Идея этого алгоритма состоит в том, чтобы пройти через все ребра этого графа один за другим в некотором случайном порядке. Это может быть любой случайный порядок. Но вы должны убедиться, что если uv (где u и v - две вершины в графе) является одним из ваших ордеров, тогда должно быть ребро от u до v . Обычно это берется непосредственно из порядка введенного ввода. Опять же, любой случайный порядок будет работать.

Выбрав порядок, мы расслабим ребра по формуле релаксации. Для данного ребра uv, идущего от u до v, релаксационная формула:

if distance[u] + cost[u][v] < d[v]
    d[v] = d[u] + cost[u][v]

То есть, если расстояние от источника до любой вершины u + вес ребра uv меньше расстояния от источника к другой вершине v , мы обновляем расстояние от источника до v . Нам нужно максимально релаксировать ребра (V-1), где V - количество ребер в графе. Почему (V-1) вы спрашиваете? Мы объясним это в другом примере. Также мы будем отслеживать родительскую вершину любой вершины, то есть когда мы расслабляем ребро, мы будем устанавливать:

parent[v] = u

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

Давайте посмотрим на пример. У нас есть график:

Мы выбрали 1 в качестве исходной вершины. Мы хотим узнать кратчайший путь от источника ко всем другим вершинам.

Сначала d [1] = 0, потому что это источник. И отдых - бесконечность , потому что мы еще не знаем их расстояния.

Мы разделим ребра в этой последовательности:

+--------+--------+--------+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |    4   |    5   |    6   |
+--------+--------+--------+--------+--------+--------+--------+
|  Edge  |  4->5  |  3->4  |  1->3  |  1->4  |  4->6  |  2->3  |
+--------+--------+--------+--------+--------+--------+--------+

Вы можете выполнить любую последовательность, которую вы хотите. Если разделить края один раз, что мы получим? Мы получаем расстояние от источника ко всем другим вершинам пути, использующему не более 1 ребра. Теперь давайте расслабляем края и обновляем значения d [] . Мы получаем:

1. d [4] + стоимость [4] [5] = бесконечность + 7 = бесконечность . Мы не можем обновить это.
2. d [2] + стоимость [3] [4] = бесконечность . Мы не можем обновить это.
3. d [1] + стоимость [1] [2] = 0 + 2 = 2 < d [2] . Итак, d [2] = 2 . Также parent [2] = 1 .
4. d [1] + стоимость [1] [4] = 4 . Итак, d [4] = 4 < d [4] . parent [4] = 1 .
5. d [4] + стоимость [4] [6] = 9 . d [6] = 9 < d [6] . parent [6] = 4 .
6. d [2] + стоимость [2] [2] = бесконечность . Мы не можем обновить это.

Мы не смогли обновить некоторые вершины, потому что условие d[u] + cost[u][v] < d[v] не совпало. Как мы уже говорили, мы нашли пути от источника к другим узлам с использованием максимального 1 ребра.

Наша вторая итерация предоставит нам путь с использованием двух узлов. Мы получаем:

1. d [4] + стоимость [4] [5] = 12 < d [5] . d [5] = 12 . parent [5] = 4 .
2. d [3] + стоимость [3] [4] = 1 < d [4] . d [4] = 1 . parent [4] = 3 .
3. d [3] остается неизменным.
4. d [4] остается неизменным.
5. d [4] + стоимость [4] [6] = 6 < d [6] . d [6] = 6 . parent [6] = 4 .
6. d [3] остается неизменным.

Наш график будет выглядеть так:

Наша третья итерация будет обновлять только вершину 5 , где d [5] будет 8 . Наш график будет выглядеть так:

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

Procedure Bellman-Ford(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
Return d

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

Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return d

Путь печати:

Чтобы напечатать кратчайший путь к вершине, мы перейдем к его родительскому элементу, пока не найдем NULL, а затем напечатаем вершины. Псевдокод будет:

Procedure PathPrinting(u)
v := parent[u]
if v == NULL
    return
PathPrinting(v)
print -> u

Сложность:

Так как нам нужно уменьшить максимум краев (V-1) , временная сложность этого алгоритма будет равна O (V * E), где E обозначает количество ребер, если мы используем adjacency list для представления графика. Однако, если adjacency matrix используется для представления графика, временной сложностью будет O (V ^ 3) . Причина состоит в том, что мы можем перебирать все ребра в O (E), когда используется adjacency list , но требуется время O (V ^ 2), когда используется adjacency matrix .

Почему мы должны максимально расслаблять все ребра (V-1) раз

Чтобы понять этот пример, рекомендуется дать краткое представление об алгоритме кратчайшего пути одиночного источника Bellman-Ford, который можно найти здесь

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

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

Давайте рассмотрим пример:

Здесь исходная вершина равна 1. Мы найдем кратчайшее расстояние между источником и всеми другими вершинами. Мы можем ясно видеть, что для достижения вершины 4 , в худшем случае, это займет (V-1) ребра. Теперь, в зависимости от порядка, в котором обнаружены края, может потребоваться (V-1) раз, чтобы обнаружить вершину 4 . Не понял? Давайте используем алгоритм Беллмана-Форда, чтобы узнать кратчайший путь здесь:

Мы будем использовать эту последовательность:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  3->4  |  2->3  |  1->2  |
+--------+--------+--------+--------+

Для нашей первой итерации:

1. d [3] + стоимость [3] [4] = бесконечность . Это ничего не изменит.
2. d [2] + стоимость [2] [3] = бесконечность . Это ничего не изменит.
3. d [1] + стоимость [1] [2] = 2 < d [2] . d [2] = 2 . parent [2] = 1 .

Мы видим, что наш релаксационный процесс только изменился d [2] . Наш график будет выглядеть так:

Вторая итерация:

1. d [3] + стоимость [3] [4] = бесконечность . Это ничего не изменит.
2. d [2] + стоимость [2] [3] = 5 < d [3] . d [3] = 5 . parent [3] = 2.
3. Он не будет изменен.

На этот раз процесс релаксации изменился d [3] . Наш график будет выглядеть так:

Третья итерация:

1. d [3] + стоимость [3] [4] = 7 < d [4] . d [4] = 7 . parent [4] = 3 .
2. Он не будет изменен.
3. Он не будет изменен.

Наша третья итерация наконец обнаружила кратчайший путь к 4 из 1 . Наш график будет выглядеть так:

Итак, для выяснения кратчайшего пути потребовалось 3 итерации. После этого, независимо от того, сколько раз мы расслабляем ребра, значения в d [] останутся неизменными. Теперь, если мы рассмотрим другую последовательность:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  1->2  |  2->3  |  3->4  |
+--------+--------+--------+--------+

Мы получим:

1. d [1] + стоимость [1] [2] = 2 < d [2] . d [2] = 2 .
2. d [2] + стоимость [2] [3] = 5 < d [3] . d [3] = 5 .
3. d [3] + стоимость [3] [4] = 7 < d [4] . d [4] = 5 .

Наша самая первая итерация нашла кратчайший путь от источника ко всем остальным узлам. Возможна другая последовательность 1-> 2 , 3-> 4 , 2-> 3 , которая даст нам кратчайший путь после 2 итераций. Мы можем прийти к решению о том, что независимо от того, как мы упорядочим последовательность, в этом примере не будет более трех итераций, чтобы узнать кратчайший путь от источника .

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

Обнаружение отрицательного цикла на графике

Чтобы понять этот пример, рекомендуется иметь краткое представление о алгоритме Беллмана-Форда, который можно найти здесь

Используя алгоритм Беллмана-Форда, мы можем определить, есть ли отрицательный цикл на нашем графике. Мы знаем, что для выяснения кратчайшего пути нам необходимо ослабить все ребра графа (V-1) раз, где V - число вершин в графе. Мы уже видели, что в этом примере после (V-1) итераций мы не можем обновить d [] , независимо от того, сколько итераций мы делаем. Или мы можем?

Если на графике есть отрицательный цикл, даже после (V-1) итераций мы можем обновить d [] . Это происходит потому, что для каждой итерации, проходя через отрицательный цикл, всегда уменьшается стоимость кратчайшего пути. Вот почему алгоритм Беллмана-Форда ограничивает количество итераций (V-1) . Если бы мы использовали Алгоритм Дейкстры , мы бы застряли в бесконечном цикле. Однако давайте сосредоточимся на поиске отрицательного цикла.

Предположим, у нас есть график:

Выберем вершину 1 как источник . После применения алгоритма алгоритма одиночного источника Беллмана-Форда к графику мы выясним расстояния от источника до всех остальных вершин.

Вот как выглядит график после (V-1) = 3 итераций. Это должно быть результатом, так как существует 4 ребра, нам нужно не более трех итераций, чтобы узнать кратчайший путь. Таким образом, либо это ответ, либо график отрицательного веса на графике. Чтобы найти, что после (V-1) итераций мы делаем еще одну заключительную итерацию, и если расстояние продолжает уменьшаться, это означает, что на графике определенно отрицательный весовой цикл.

В этом примере: если мы проверим 2-3 , d [2] + стоимость [2] [3] даст нам 1, что меньше, чем d [3] . Поэтому мы можем заключить, что на нашем графике есть отрицательный цикл.

Итак, как мы узнаем отрицательный цикл? Мы немного модифицируем процедуру Bellman-Ford:

Procedure NegativeCycleDetector(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return "No Negative Cycle"

Вот как мы узнаем, есть ли отрицательный цикл на графике. Мы также можем модифицировать алгоритм Bellman-Ford для отслеживания отрицательных циклов.