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

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

0 голосов
/ 28 декабря 2018

Я пытался реализовать алгоритм 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 приводит к обнаружению цикла

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

1 Ответ

0 голосов
/ 28 декабря 2018

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

Алгоритм Беллмана-Форда просто ослабляет все ребра и делает это |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| раз, что говорит о существовании отрицательного (ых) цикла (ов).

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

...