Алгоритм Беллмана-Форда для объяснения отрицательных циклов

Question

Я попытался реализовать алгоритм BF для обнаружения отрицательного цикла.

Я следовал лекционным заметкам, чтобы реализовать алгоритм. Мое решение было следующее:

def belman_ford(s, adj, cost):
    arr_len = len(adj)
    dist_arr = [MAX_VAL]*arr_len
    prev_arr = [None]*arr_len
    dist_arr[s] = 0

    for u in range(arr_len):
        for i, v in enumerate(adj[u]):
            if dist_arr[v] == MAX_VAL:
                break
            if dist_arr[v] > dist_arr[u] + cost[u][i]:
                dist_arr[v] = dist_arr[u] + cost[u][i]
                prev_arr[v] = u


    #detect negative cycle
    for u in range(arr_len):
        for i, v in enumerate(adj[u]):
            if dist_arr[v] == MAX_VAL:
                break
            if dist_arr[v] < dist_arr[u] + cost[u][i]:
                return 1

    return 0


def negative_cycle(adj, cost):
    #write your code here
    return belman_ford(0,adj, cost)

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

def negative_cycle(adj, cost):
    distance=[0]*len(adj)
    distance[0] = 0
    for ind in range(len(adj)):
        for u in range(len(adj)):
            for v in adj[u]:
                v_index = adj[u].index(v)
                if distance[v] > distance[u] + cost[u][v_index]:
                    distance[v] = distance[u] + cost[u][v_index]
                    if ind==len(adj) - 1:
                        return 1
    return 0

Я не могу понять логику этого. Почему на самом деле это if ind==len(adj) - 1 оператор if ведет к обнаружению цикла

В качестве входных данных я получаю список смежности и стоимости

Answer 1

Для основной идеи алгоритма Беллмана-Форда, вот небольшой обзор из Википедии:

алгоритм Беллмана – Форда просто ослабляет все ребра, и делает это |V|-1 раз, где |V| это количество вершин в графе.

Тогда объяснение вашей линии if ind==len(adj) - 1 является

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

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

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

S --> A --> B --> C --> D --> E --> F --> G --> H --> I

Теперь скажите, что у вас есть график без отрицательных циклов. Скажем, у него есть 10 вершин, вам нужно не более 9 релаксаций, чтобы достичь (получить кратчайший путь) самой дальней вершины из источника. Что если после 9 расслаблений у вас все еще есть улучшения? У вас должны быть отрицательные циклы на вашем графике.

ind в вашем коде есть счетчик. когда ind == len(adj) - 1 это означает, что у вас есть свободные расстояния для |V| раз, который говорит о существовании отрицательного цикла (ов).

Также проверьте третью страницу с последней в вашей заметке.