Получение неправильного ответа при поиске отрицательного цикла

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

Вот код Python, который я написал:

def bellman_ford(n, edges):
    dist = [float('inf')] * (n + 1)
    dist[1] = 0
    prev = [-1] * (n + 1)
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and  dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
    for u, v, w in edges:
        if dist[u]!=float('inf') and dist[u] + w < dist[v]:
            cycle = [v]
            prev[v] = u
            while u != v:
                cycle.append(u)
                u = prev[u]
            cycle.append(v)
            return True, cycle[::-1]
    return False, None
n, e = map(int, input().split())
edges = []
for _ in range(e):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))

chk, cycle = bellman_ford(n, edges)
if chk == True:
    print("YES")
    print(*cycle)
else:
    print("NO")

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

Заранее спасибо за вашу помощь!

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

Alois Christen 06.06.2024 10:54

@AloisChristen, я отредактировал это... не мог бы ты помочь сейчас?

Anand Singh1 06.06.2024 11:34

Что происходит, когда граф не связен?

Timus 06.06.2024 16:24
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
3
102
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

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

Прагматичным решением является следующее:

  • Удалите из графа все узлы, у которых нет исходящих ребер или входящих ребер. Повторяйте до тех пор, пока больше узлов нельзя будет удалить.

  • Запустите алгоритм Беллмана-Форда на первом узле, который все еще является частью графа.

  • Проверьте, найден ли цикл. Если да, верните его.

  • Проверьте, все ли узлы получили конечное расстояние. Если да, то верните, что цикла нет.

  • Удалите из графа все узлы, получившие конечное расстояние, и их соединенные ребра.

  • Повторите сверху.

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

Другие вопросы по теме