The Gateway to Computer Science Excellence
0 votes
114 views
Can we use DFS to detect the negetive weight cycle in a directed graph?
in Algorithms by Active (4.8k points) | 114 views
+1
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.
0
Is this algorithm would be better than Bellman-Ford with time complexity O(V+E) ?
0
Offcourse.

1 Answer

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.
by Active (4.8k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,356 answers
198,483 comments
105,254 users