CODEWITHSUNDEEP
javaalgorithmgraphcyclebellman-ford
Chase
Chase

Reputation: 69

Bellman Ford's algorithm with negative cycles

So if I'm trying to find the shortest path using Bellman Ford's algorithm using this method to test if there is a path:

public boolean hasPath(int v){
    return distTo[v] < Double.POSITIVE_INFINITY;
}

If I have a negative cycle then what happens to this algorithm? Does it still return true because I know that Dijkstra's algorithm doesn't work with negative cycles but what about Ford's?

Upvotes: 0

Views: 459

Answers (1)

Juan Lopes
Juan Lopes

Reputation: 10565

It will work, but the value may or may not be the shortest path. The real shortest path may be actually negative infinity, because if the negative circle reaches the destination node, there will be always a shorter path than the current shortest path.

This is actually how you use Bellman-Ford to detect negative circles. If after |V| loops, the (|V|+1)th still updates some shortest path, there is a negative circle in the graph.

Upvotes: 2

Related Questions