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