Advertisement
Iam_Sandeep

Negative weight cycle Bellman Ford

Jun 26th, 2022
816
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.80 KB | None
  1. #User function Template for python3
  2. #T.C=O(ev)
  3. #initially we select a vertex as source and find out the distance to other vertices .
  4. #we relax n-1 iterations. If we found any changes at nth iteration it means there is a negative edge cycle
  5. class Solution:
  6.     def isNegativeWeightCycle(self, n, edges):
  7.         dis=[float('inf')]*n
  8.         dis[0]=0
  9.         for _ in range(n-1):
  10.             update=False
  11.             for i,j,k in edges:
  12.                 if dis[j]>dis[i]+k:
  13.                     dis[j]=dis[i]+k
  14.                     update=True
  15.             if update==False:
  16.                 return False
  17.         update=False
  18.         for i,j,k in edges:
  19.             if dis[j]>dis[i]+k:
  20.                 dis[j]=dis[i]+k
  21.                 update=True
  22.         return update==True
  23.        
  24.  
  25.            
  26.  
Advertisement
RAW Paste Data Copied
Advertisement