fork download
copy 
  1. def relax(u,v,w,dist,prev):
  2.     if dist[u]+w < dist[v]:
  3.         dist[v] = dist[u]+w
  4.         prev[v] = u
  5.  
  6. def bellmanFord(V,E):
  7.     dist = [float('inf')] * V
  8.     prev = [None] * V
  9.     dist[0] = 0
  10.  
  11.     for i in range(V-1):
  12.         for edge in E:
  13.             relax(edge[0],edge[1],edge[2],dist,prev)
  14.  
  15.     #checks for negative cycles        
  16.     for e in E:
  17.         u = e[0]
  18.         v = e[1]
  19.         w = e[2]
  20.         if dist[u]+w < dist[v]:
  21.             return 1
  22.  
  23.     return 0
  24.  
  25. edges = []
  26. edges.append([0, 1, 5])
  27. edges.append([2, 3, -5])
  28. edges.append([3, 4, -6])
  29. edges.append([4, 2, -5])
  30. edges.append([1, 2, 5])
  31.  
  32. print(bellmanFord(5, edges))
  33.  
  34.  
  35.  
Success #stdin #stdout 0.02s 7200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/4oXrb9
language:
Python (cpython 2.7.16)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!