Я работал над реализацией алгоритма Беллмана-Форда в 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")
Я провел множество пробных прогонов, но не смог точно определить недостаток в моей реализации. Буду очень признателен за любую помощь в определении того, где я ошибся.
Заранее спасибо за вашу помощь!
@AloisChristen, я отредактировал это... не мог бы ты помочь сейчас?
Что происходит, когда граф не связен?
Алгоритм Беллмана-Форда находит кратчайшие расстояния до всех узлов от одного выбранного узла, которым в вашем случае является узел 1. Алгоритм найдет отрицательный цикл только в том случае, если этот цикл может быть достигнут из узла 1. Например, если у вас есть следующее: входной график:
...тогда отрицательный цикл между узлами 2 и 3 не будет обнаружен просто потому, что расстояния между их узлами никогда не становятся меньше бесконечности.
Прагматичным решением является следующее:
Удалите из графа все узлы, у которых нет исходящих ребер или входящих ребер. Повторяйте до тех пор, пока больше узлов нельзя будет удалить.
Запустите алгоритм Беллмана-Форда на первом узле, который все еще является частью графа.
Проверьте, найден ли цикл. Если да, верните его.
Проверьте, все ли узлы получили конечное расстояние. Если да, то верните, что цикла нет.
Удалите из графа все узлы, получившие конечное расстояние, и их соединенные ребра.
Повторите сверху.
В качестве альтернативы вы можете сначала запустить один из алгоритмов, чтобы идентифицировать компонент на графике, а затем один раз запустить алгоритм для этого компонента. Затем повторяйте до тех пор, пока не останутся компоненты.
Пожалуйста, вставьте формулировку проблемы внутри вопроса. Вопрос должен быть самодостаточным, без какой-либо ссылки на внешний ресурс. Кроме того, добавьте несколько примеров проведенных вами тестов, ожидаемых результатов и фактических результатов.