# How can I determine if there is a closed-loop path in a graph?

Assuming I have a computer representation of a graph presented in the figure below: How can I find out whether there are some close-loops inside the graph, like the one marked in red (or more complicated ones)? In other words I need to create an algorithm that will check if there are some "recurencies" in the graph. By recurencies I mean the situation where one node will be producing results that will be used further down by nodes that are inputs to the first node.

Any tips, key words or directions where to look for the solution will be much appreciated. I am new to the subject so please let me know if something needs more explanation.

One approach would be to assign a weight of $$-1$$ to all nodes in the graph and use one extra update on top of the regular $$n$$ updates of the Floyd-Warshall algorithm to detect if there is a negative cost cycle in the graph.
This works because having a cycle in the original graph is equivalent to having a negative cost cycle in the $$-1$$ weighted graph.
If there are $$n$$ vertices in the graph, the algorithm would run in $$\Theta(n^3)$$ time and use $$\Theta(n^2)$$ space.
Another approach that would be faster and of less space is to check if a depth first search on the graph ever brings you back to a node you’ve already seen. If you have $$n$$ vertices and $$m$$ edges in the graph, this would take $$\Theta(n+m) = \mathcal{O}(n^2)$$ time and $$\Theta(n)$$ space.