Implementation of Bellman-Ford algorithm in python

Question

I am doing an exercise for the course "Algorithms on Graphs" on Coursera and I have to implement the Bellman-Ford algorithm to detect if a graph has a negative cycle or not, outputting 1 and 0 respectively. I did a lot of stress testing and my implementation works fine, but it fails on one of the test cases on the course (but they don't give any information about it, other than "wrong answer"). My implementation is just the same one you find all over the web, and because of that I can't see what is wrong with my code. Any ideas?

def relax(u,v,w,dist,prev):
    if dist[u]+w < dist[v]:
        dist[v] = dist[u]+w
        prev[v] = u

def bellmanFord(V,E):
    dist = [float('inf')] * V
    prev = [None] * V
    dist[0] = 0

    for i in range(V-1):
        for edge in E:
            relax(edge[0],edge[1],edge[2],dist,prev)

    #checks for negative cycles        
    for e in E:
        u = e[0]
        v = e[1]
        w = e[2]
        if dist[u]+w < dist[v]:
            return 1

    return 0

Answer 1

This code does not work for graphs that are not connected eg it gives 1 for the following case which is correct:

edges = []
edges.append([0, 1, 5])
edges.append([2, 3, -5])
edges.append([3, 4, -6])
edges.append([4, 2, -5])
edges.append([1, 2, 5])

print(bellmanFord(5, edges))

Link to demo : http://ideone.com/j8XAs3

and when we remove the edge 1 -> 2 it gives it gives 0, even though the graph has a negative cycle (2 -> 3 -> 4 -> 2) :

edges = []
edges.append([0, 1, 5])
edges.append([2, 3, -5])
edges.append([3, 4, -6])
edges.append([4, 2, -5])

print(bellmanFord(5, edges))

Link to demo : http://ideone.com/N4Bljk

---

EDIT:

As you said that the test case #12 passed after you used every vertex as source, I do believe that the graph is not connected, the problem is that the time complexity of the solution has increased it is now O(n*n*m) i.e about 10^11 operations that is certain to time out.

So you can modify the algorithm in the following way :

1) Find all the connected components and separate out the vertices and edges for that component and create a new graphs with those vertices and edges

2) Suppose you have k new graphs now, run Bellman Ford on each of them.

Also you are using the word "strongly connected" in the wrong way, a directed graph is strongly connected if there is a path from every vertex to every other possible vertex.

I saw the question that you are referring to, I assume it is "Problem: Detecting Anomalies in Currency Exchange Rates" if I am right regarding the question then the example given in the question contradicts the fact that it is strongly connected as there is no way to reach the vertex 4, the graph however is connected.

Example in the question :

4 4
1 2 -5
4 1 2
2 3 2
3 1 1

Do let me know if it is not the question you are referring to, or if you have some other doubts.

Answer 2

So, I found the solution for the exercise and it was pretty simple. The problem was using float('inf') to initialize the dist list. If instead I use a huge number, like 10000000 it works fine on my initial code, without the need to scan all the vertices. It works algo in the example of a not connected graph. Thanks forr the help, I learned a lot!