Relaxation in Bellman Ford

[choprasaurav7]

1. If I understand the algorithm correctly, since we need to do relaxation n-1 times shouldn't the loop run from i=0; i<=V-1 ?
   

   Algorithms/src/main/java/com/williamfiset/algorithms/graphtheory/BellmanFordAdjacencyList.java

   Line 57 in 65dcc1b

   for (int i = 0; i < V - 1; i++)

2. why do we need to check for negative cycle n-1 times again? Can we just loop over the edges to see if distance is decreasing and detect negative cycle?
   

   Algorithms/src/main/java/com/williamfiset/algorithms/graphtheory/BellmanFordAdjacencyList.java

   Line 66 in 65dcc1b

   for (int i = 0; i < V - 1; i++)

[josephAttia]

@choprasaurav7

1. Having int i = 0; i < V - 1; ++i will take into account the initial state, that is to say 0, so why would we need to reach the termination state fully at V - 1 since we are starting at 0 (first iteration)? Having your proposed change <= will result in the terminating state to go one above the original i < V - 1 making the end state V not the required V - 1. Hope that helps

[sevillaarvin]

There's also a response here but I still don't get it. #108 (comment)

All other bellman-ford implementations I see on the internet only loop through the edges once to detect a negative cycle.

• https://en.wikipedia.org/wiki/Bellman–Ford_algorithm#Algorithm
• https://www.w3schools.com/dsa/dsa_algo_graphs_bellmanford.php
• https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf