Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #User function Template for python3
- #T.C=O(ev)
- #initially we select a vertex as source and find out the distance to other vertices .
- #we relax n-1 iterations. If we found any changes at nth iteration it means there is a negative edge cycle
- class Solution:
- def isNegativeWeightCycle(self, n, edges):
- dis=[float('inf')]*n
- dis[0]=0
- for _ in range(n-1):
- update=False
- for i,j,k in edges:
- if dis[j]>dis[i]+k:
- dis[j]=dis[i]+k
- update=True
- if update==False:
- return False
- update=False
- for i,j,k in edges:
- if dis[j]>dis[i]+k:
- dis[j]=dis[i]+k
- update=True
- return update==True
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement