Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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


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

Browse other questions tagged or ask your own question.