445 views
0 votes
0 votes
Can we use DFS to detect the negetive weight cycle in a directed graph?

1 Answer

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.

Related questions

2 votes
2 votes
1 answer
2
0 votes
0 votes
0 answers
4