# Distance vector in a weighted graph

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?

• try looking over the proof of the Djikstra Algorithm Essentially, what you are asking is "why Djikstra works?" Nov 4 '15 at 15:33

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.
• 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. Nov 4 '15 at 18:40