0 votes 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 asked Nov 4, 2016 vaishali jhalani 462 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Prashant. commented Nov 4, 2016 reply Follow Share 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 votes 1 votes vaishali jhalani commented Nov 4, 2016 reply Follow Share Is this algorithm would be better than Bellman-Ford with time complexity O(V+E) ? 0 votes 0 votes Prashant. commented Nov 4, 2016 reply Follow Share Offcourse. 0 votes 0 votes Please log in or register to add a comment.
0 votes 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 See all 0 reply Please log in or register to add a comment.
