This lesson's interactive features are locked, please to keep using them
Cycles in Graphs
A cycle in a graph is any path that starts and ends at the same node, without repeating any other nodes along the way. The presence of a cycle isn't a problem in itself; it just means that you can get back to a starting node after traversing a series of edges.
Cycles can occur in all the types of graphs that we've discussed: directed and undirected, weighted and unweighted. Look at the following weighted, undirected graph. Any node can be returned to after looping through the others.
Graphs With Negative Weights
But a problem can arise when a weighted graph has negative edge weights. It can confuse a path-finding algorithm like Dijkstra's, which assumes that once a node is visited, the "shortest" path to it has been found.
As long as all weights are positive, Dijkstra's assumption is correct. Look at what happens, though, if we introduce a negative weight.
In this graph, Dijkstra's algorithm will find the path src -> B -> dest, with a total cost of 1,379. It's not designed to understand that the path src -> A -> B -> dest could have a lower weight, i.e. 1,305.
Negative Cycles
In fact, the graph shown above has an even bigger problem: because it's undirected, the negative weight allows for a negative cycle. We could theoretically go back and forth between nodes A and B forever, with the "total cost" of the path approaching negative infinity.
Any negative edge weight in an undirected graph creates a negative cycle, which can make the question of path-finding nonsensical. If a graph is going to have negative weights, it should be directed. That way, negative cycles are usually avoided – though they can still occur in a poorly designed directed graph.
If we take the last graph and make it directed, you can see that there's no longer a negative cycle, despite the negative weight.
There is a clear optimal path, i.e. src -> A -> B -> dest, with a total cost of 1,305. Dijkstra's algorithm still can't find it, but that's why we have the Bellman-Ford algorithm, which we'll be learning about in this chapter. Bellman-Ford is designed to handle negative weights and to detect cycles.
For good measure, let's look at an example of a directed graph with a negative cycle. Can you spot it?