Triangular inequality in weighted graphs

1.2k Views Asked by At

In a finite directed complete graph $G ( V, E )$, if all edges have weight either $1$ or $2$, how to show that weights of edges of $G$ satisfies "Triangular Inequality"?

Edited

Where triangular inequality is weight of any edge is less than or equal to the sum of weights of any other two edges (ALWAYS)

1

There are 1 best solutions below

4
On

given an edge, it has weight 1 or 2, that is always less or equal to the sum of the weights of two edges.

This means that, if we define $d(u,v)$ as the minimum distance between the nodes $u$ and $v$, we have $1\le d(u,v)\le 2$, and so $$d(u,v)\le 2=1+1\le d(u,w)+d(w,v)$$ since every pair of nodes is connected by an edge.