= Path metric
{title2=$\rho$}
{wiki}
Given positive <edge lengths> $\ell(e)$ on a <graph>, define the distance between two <vertices> by
$$
d(u,v)=\inf_{\gamma:u\leadsto v}\sum_{e\in\gamma}\ell(e),
$$
where $\gamma$ ranges over finite <graph paths>. An absent path gives distance $+\infty$. On a finite <connected graph>, this is a <metric>: reversing and concatenating routes gives symmetry and the <triangle inequality>, while the least <edge length> bounds every nonempty path away from zero. It is also a <metric> on a connected <locally finite graph>, since every path leaving a fixed <vertex> pays at least the positive minimum of its finitely many incident <edge lengths>.
Positive <edge lengths> alone do not guarantee a <metric> on an arbitrary infinite <graph>. Join two <vertices> $u,v$ through intermediate <vertices> $z_n$, with both <edges> $uz_n,z_nv$ having length $1/n$. Then $d(u,v)\leq2/n$ for every $n$, so distinct <vertices> have distance zero. On each finite-distance component the general construction is a <pseudometric>; its zero-distance classes give a <metric quotient>.
Back to article page
