CODEWITHSUNDEEP
graph-theorygraph-algorithmshortest-pathgraph-traversalbellman-ford
VITTHAL BHANDARI
VITTHAL BHANDARI

Reputation: 179

Does negative cycle detection using Bellman Ford depend upon the choice of starting node?

I have been doing the following problem CSES Problem : Cycle Finding which requires me to find and print a negative cycle in a directed graph. Bellman Ford can solve the problem but I've observed that 1-2 test cases (out of a total 18) always fail depending upon the choice of starting node.

Does this mean that in a DIRECTED GRAPH, Bellman Ford is subject to choice of starting node? Because I haven't faced a similar issue in undirected graph.

Consider the following test case : A simple directed graph here if I start with 1, I won't detect a negative cycle. However if i start with 3, I can detect it. What to do ?

Upvotes: 0

Views: 1575

Answers (3)

bg_color
bg_color

Reputation: 11

The starting point shouldn't matter in Bellman-Ford as far as detecting -ve weight cycle is concerned. In the above case dist[2]=inf initially but after every i'th iteration its distance from starting node will decrease 1 unit as dist[2]=min(dist[2],dist[2]+(-1)) because of the edge (2,2,-1). And so the dist[2] will also decrease in the nth iteration, which cycle -ve cycle-detecting step.

Upvotes: 1

Mokrall
Mokrall

Reputation: 80

Yes, the starting node does matter, as the Bellman Ford algorithm will find a negative cycle only if it's reachable from the starting node. But you can use an easy trick, that will help you find a negative cycle not depending on the starting node, without changing the algorithm's complexity. Just add a fictional node with edges foing from it to all other nodes, weighted 0. Than run the Ford Bellman algorithm from this fictional node.

Upvotes: 1

zggf
zggf

Reputation: 46

Bellman Ford algorithm will detect negative cycles if they are reachable from the starting node. In undirected connected graph we don’t have this problem because all nodes are reachable from any node. To solve this problem in directed graph we can add one node and connect it to all the other nodes using directed edges with weight 0. It won’t create any new cycles. This method is also used in Johnson's algorithm for all-pairs shortest path problem.

Upvotes: 2

Related Questions