This is questions regarding bellman ford algorithm in graph .

Question

What if we use one variable as bool type ( let say check , marks it false in starting ) , if there will be any updation in distance then we mark it as true otherwise it will be false . Then if we achieve shortest path before n-1 times , then we know it. It will be optimised approch .

https://code.sololearn.com/cFSz6HWorK3y/?ref=app

Answer 1

Yes, this is an optimized approach to the Bellman-Ford algorithm. Instead of running the algorithm for n-1 times, you can check the boolean variable to determine if any changes have been made to the distances. If the boolean is still false after one iteration, then you know that no more updates can be made, and that you have found the shortest path.