2
$\begingroup$

I got a weighted, connected and directed graph $G$. There is a vector called the distance vector $Dv \in \mathbb{N}^n$ in which $Dv_i$ is the shortest distance from $1$ to $i$. All edge weights are positive integers. I have to show that every distance vector $Dv$ satisfies:

  1. $Dv_1 = 0$.

  2. For all $j \neq 1$ there exists $i$ such that $Dv_j = Dv_i + w(i,j)$.

  3. For all $i,j$ it holds that $Dv_j \leq Dv_i + w(i,j)$.

I think that 1 is trivial: from 1 to 1 you have no distance. But the rest? Can you give me an idea how to prove 2 and 3?

$\endgroup$
1
  • 5
    $\begingroup$ try looking over the proof of the Djikstra Algorithm Essentially, what you are asking is "why Djikstra works?" $\endgroup$
    – jjohn
    Nov 4 '15 at 15:33
1
$\begingroup$

Hint for 2: If $1,\ldots,i,j$ is a shortest path from $1$ to $j$ then $1,\ldots,i$ is a shortest path from $1$ to $i$.

Hint for 3: If $1,\ldots,i$ is a path from $1$ to $i$ then $1,\ldots,i,j$ is a path from $1$ to $j$.

In both cases $\ldots$ represents some list of vertices.

$\endgroup$
7
  • $\begingroup$ Thanks for your replay. I think I have to show both directions because it is some sort of "if and only". To show the "=>" direction I just have to paint a grah 1->2->3 should be ok because all 3 terms are true. To 2. I think I got it with your help. If 1,...i,j is a shortest path than it has the same value as Dv_j and 1,...,i has to be the same as Dv_i. So that Dv_i -w(i,j) is equal to Dv_j. Is that right? $\endgroup$
    – Asker
    Nov 4 '15 at 17:49
  • $\begingroup$ That's not what if and only if means in this context. It means that you have to show that if $Dv$ is a distance vector then it satisfies all three properties, and conversely, if $Dv$ satisfies all three properties then it is a distance vector. $\endgroup$ Nov 4 '15 at 18:40
  • $\begingroup$ For the "Dv satisfies all properties => it is a distance vector" direction, is it enough to show a single vektor which satisfies the properties and then show that it is the shortest? And to make it more clear to me, what is Dv exactly ? I know that Dv_i is a shortest path form 1 to i but without an index I can not interpret Dv. $\endgroup$
    – Asker
    Nov 4 '15 at 18:52
  • $\begingroup$ For the "Dv satisfies all properties => it is a distance vector" you need to show that if Dv is a vector satisfying the properties then Dv_i is the length of the shortest path from 1 to i. Here Dv is the vector whose i'th coordinate is Dv_i. $\endgroup$ Nov 4 '15 at 22:12
  • 1
    $\begingroup$ Perhaps it's best if you first gave it a try. In real life there won't always be someone to give you hints all the time. $\endgroup$ Nov 4 '15 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.