4
$\begingroup$

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.

  • 0
    @amir: You can answer your own question and mark it as accepted.2012-04-09

0 Answers 0