if i want to find the lightest(minimum weight) path from x to y in a directed graph and i use the Bellman Ford algorithm but instead of starting normally from x, i start the iterations from y, is it guaranteed that i will NOT finish the calculation of the lightests paths before the last iteration? meaning before the |V|-1 iteration. and if so, can someone explain why? I know the order of the scan is very important, but I cant seem to point out why exactly does this specific way of scanning does the worst job out of every other possibility. maybe there's another way of guaranteeing to not finish all the necessary calculations before the last iteration?
Thank you all.
Consider a graph which has a single path through it: Vertex v connects only to vertex v+1. All edges have cost 1. If you process all the edges in forwards order from v1, all weights get updated in the first pass, and end up being the final weights. But if you iterate through them backwards, then in the first pass only one weight (that of vertex 2) gets updated. In the second iteration, only vertex 3 gets updated. And so on. A good ordering of edges will allow more information to propagate during a single pass.