Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.