Inequality of distances in a graph

47 Views Asked by At

Certainly it's obvious but I can't catch the reason behind it.

Why do we have :

Let $D= (V,A)$ be a directed graph, $w:A \to \mathbb R$ be arc weights and $s \in V$. Denote with $d(s,v)$ the length of the shortest path from $s$ to $v$ in $D$, subject to $w$.

If there are no negative cycles in $D$, then we have $$ \forall (u,v) \in A : d(s,v) \leq d(s,u) + w(u,v) $$ (or equivalently $$ \forall (u,v) \in A : d(s,v)- d(s,u) \leq w(u,v)). $$

I don't understand what's the inner thoughts of this sentence : $$d(s,v) \leq d(s,u) + w(u,v) $$ I don't know if it comes from the definition of distance on the graph (which I only know how to compute using the Bellman Ford algorithm), from a triangular inequality or from anything else. How do you know that one side is less than the other ? When do we have equality, strict inequality ?

1

There are 1 best solutions below

4
On BEST ANSWER

$d(s,v)$ is the weighted length of the shortest path from $s$ to $v$.

$\exists (u,v):d(s,v) > d(s,u) + w(u,v)$ is a contradiction, because going from $s$ to $u$ and then by that $(u,v)$ arc is a shorter path than whatever path $d(s,v)$ takes.