Как проверить, есть ли в графике отрицательный цикл, но он не может быть получен из источника?

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

def negative_cycle(adj, cost):
    dist = [float('inf')] * n
    prev = [None] * n
    dist[0] = 0
    for _ in range(n-1):
        for u, edges in enumerate(adj):
            for i, v in enumerate(edges):
                if dist[v]>dist[u]+cost[u][i]:
                    dist[v]=dist[u]+cost[u][i]
                    prev[v]=u
    for u, edges in enumerate(adj):
        for i, v in enumerate(edges):
            if dist[v]>dist[u]+cost[u][i]:
                return 1
    return 0

python-3.x graph shortest-path bellman-ford
person Adithya Swaroop    schedule 18.07.2019    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

person amirali    schedule 24.08.2019

arrow_upward
0
arrow_downward

Если вам не важен кратчайший путь и вы просто хотите обнаружить отрицательный цикл, вы можете установить начальное расстояние для всех вершин равным 0. Это имеет тот же эффект, что и создание воображаемого источника s и соединение s со всеми остальными вершинами с ребрами веса 0.

Тогда ваш код будет выглядеть так, как показано ниже (возможно, я не знаю Python, поэтому мой синтаксис может быть неправильным).

def negative_cycle(adj, cost):
    dist = [0] * n
    prev = [None] * n
    for _ in range(n-1):
        for u, edges in enumerate(adj):
            for i, v in enumerate(edges):
                if dist[v]>dist[u]+cost[u][i]:
                    dist[v]=dist[u]+cost[u][i]
                    prev[v]=u
    for u, edges in enumerate(adj):
        for i, v in enumerate(edges):
            if dist[v]>dist[u]+cost[u][i]:
                return 1
    return 0
person KonaeAkira    schedule 01.05.2020