pythonalgorithmgraphbellman-fordcycle-detection

Getting wrong answer while find a negative cycle

I've been working on implementing the Bellman-Ford algorithm in Python to detect negative cycles for the problem linked above. However, I've hit a roadblock. Despite my efforts, I've encountered incorrect answers and frequent Time Limit Exceeded (TLE) errors for the Problem.

Here's the Python code I've written:

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")

I've conducted numerous dry runs, but I'm unable to pinpoint the exact flaw in my implementation. Any assistance in identifying where I've gone wrong would be greatly appreciated.

Thank you in advance for your help!

Solution

  • The Bellman-Ford algorithm finds shortest distances to all nodes from one selected node, which in your case is node 1. The algorithm will find a negative cycle only if that cycle can be reached from node 1. For instance, if the following is your input graph:

    enter image description here

    ...then the negative cycle between nodes 2 and 3 will not be detected, simply because their node's distances never get any less than infinity.

    A pragmatic solution is to do the following:

    Alternatively you could first run one of the algorithms to identify a component in the graph, and then run the algorithm once on that component. Then repeat as long as there are components left.