Bellman-ford algorithm for negative cycles explanation

Question

I tried to implement BF algorithm for negative cycle detection.

I followed the lecture notes to implement algorithm. My solution was the following:

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)

However I found another solution that helped me to pass coding challenge.

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

I can't understand the logic behind it. Why actually this if ind==len(adj) - 1 if statement leads to the cycle detection

As an input I get the adjacency and cost list

Answer 1

For the basic idea of Bellman-Ford algorithm, here's some quick review from Wikipedia:

the Bellman–Ford algorithm simply relaxes all the edges, and does this |V|-1 times, where |V| is the number of vertices in the graph.

Then the explanation for your line if ind==len(adj) - 1 is

Since the longest possible path without a cycle can be |V|-1 edges, the edges must be scanned |V|-1 times to ensure the shortest path has been found for all nodes.

A final scan of all the edges is performed and if any distance is updated, then a path of length |V| edges has been found which can only occur if at least one negative cycle exists in the graph.

Bellman-Ford assumes that distances are very large (infinity) at first, then gradually brings them down to the lowest possible. This is called relaxation. In each iteration, the edges one step farther from the source get relaxed.

S --> A --> B --> C --> D --> E --> F --> G --> H --> I

Now say you have a graph with no negative cycles. Say it has 10 vertices, you need no more than 9 relaxations to reach (get the shortest path of) the farthest vertex from the source. What if after 9 relaxations you still get improvement? You must have negative cycles in your graph.

The ind in your code is a counter. When ind == len(adj) - 1 it means you have relaxed distances for |V| times, which tells the existence of negative cycle(s).

Also check out the third page from last in your own note.