title: Implementation of Bellman-Ford algorithm in python
body: <p>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?</p>
  
  <pre><code>def relax(u,v,w,dist,prev):
      if dist[u]+w &lt; 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 &lt; dist[v]:
              return 1
  
      return 0
  </code></pre>