# Bellman-Ford algorithm with changes

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<j) do
Relax (v_j,v_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.

-
Hint(?): Consider the subgraph consisting only of the up-edges. Think about the edges in any path s to $v_j$, and think which of those edges have been relaxed. –  ShreevatsaR Apr 29 '11 at 21:16
@shreevatsaR Thank you! It's help me a lot –  Amir Apr 30 '11 at 17:46
@amir: You can answer your own question and mark it as accepted. –  user28579 Apr 9 '12 at 17:30