In Bellman ford algorithmThe , one has to findBellman-Ford algorithm determines the shortest partpath from all vertex to a source vertex s$s$ to all other vertices. Initially the distance between $s$ and all other vertices beside s is madeset to infinity$\infty$. Then each nodethe shortest path from s is calculated and least distance$s$ to each vertex is computed,computed; this goes on for upto V-1 times $|V|-1$ iterations. My questions are:
- Why does there need to be $|V|-1$ iterations?
- Would it matter if I checked the edges in a different order?
Say, if I first check edges 1,2,3, but then on the second iteration I check 2,3,1.
My question is first why is it upto V-1 times and my second question is would it matter if I did not check the edges in the order so say suppose I check edge 1,2,3 then second iteration I check 2,3,1 . I was watching a mit video and profMIT Prof.Eric Eric said that it did notthe order didn't matter, which is a bit confusing say suppose Ibut this confuses me: wouldn't the algorithm incorrectly update a node based on edge x whose$x_2$ if its value could have beenwas dependent on the next edge x2$x_1$ but because the second time I updated some other say suppose x2, the node did not increase the value as it$x_1$ is supposed to.updated after $x_2$?
