Consider this simple graph:
S -> A -> B -> C
In CLRS, the authors have implemented a loop which goes for |V|-1.
But according to path-relaxation property a simple path P can be < s,a,b,c >.
Using the path-relaxation property we are going to relax the edges of P in the following order
(S,A),(A,B),(B,C)
So, we will be done in a single pass for our |V| - 1 iterations. I can understand the use of |V| -1 passes, had the path-relaxation property not specified that we relax the path, starting from 'the source'.
What's the point of |V| - 1 iterations here? Where am I going wrong, with the explanation.
Because the any shortest path between any two nodes can't contain greater than |V| nodes or |V|-1 edges. By relaxing the edges for |V|-1 times we are sure that we have got the optimal distance between two nodes ( if there at all exists a optimal path).