Relaxation in Bellman Ford

[choprasaurav7]

trafficstars

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 ? https://github.com/williamfiset/Algorithms/blob/65dcc1bb0eea241d4c32c9c676540920d037bb76/src/main/java/com/williamfiset/algorithms/graphtheory/BellmanFordAdjacencyList.java#L57

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? https://github.com/williamfiset/Algorithms/blob/65dcc1bb0eea241d4c32c9c676540920d037bb76/src/main/java/com/williamfiset/algorithms/graphtheory/BellmanFordAdjacencyList.java#L66

[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