0 0 votes Can we use DFS to detect the negetive weight cycle in a directed graph? Algorithms algorithms graph-algorithms depth-first-search + – vaishali jhalani 932 views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply Prashant. commented Nov 4, 2016 reply Follow flag Do one simple thing with each function call add new function call ie. length to new vertex .. this way in end u can chek when cycle is present in graph sum is positive or negative. 1 1 replyShare vaishali jhalani commented Nov 4, 2016 reply Follow flag Is this algorithm would be better than Bellman-Ford with time complexity O(V+E) ? 0 0 replyShare Prashant. commented Nov 4, 2016 reply Follow flag Offcourse. 0 0 replyShare Please log in or register to add a comment.
0 0 votes Yes Possible. If there is a Back Edge (u,v) in a DFT , there is a cycle in the graph G. Total Cost from v to u + Back Edge Cost(u,v) <0 indicates there is a negative weighted cycle in the graph G. Arnab Bhadra answered Jun 18, 2017 Arnab Bhadra comment Share Follow 0 reply Please log in or register to add a comment.
