I got this question and I will be happy for a clue.
Here is a similar algorithm to the Bellman-Ford algorithm:
for i=1 to |(n-1)/2| do for j = 1 to n-1 do for each (v_j,v_k) : (k>j) do Relax (v_j,v_k) for j = n to 2 do for each (v_j,v_k) : (k
where we define the "up-edge" as $e=(v_j,v_k),\quad k > j$.
I need to prove that for each lightest path from $s$ to $v_j$ which compose of "up-edge"s only - $d(v_j)=T(s,v_j)$ in the first iteration ($T$ is the smallest path between $s$ to $v_j$ in the graph).
It makes sense, but I can't prove it. I tried to prove it by contradiction, but without success.
Any suggestions? Thank you.