# Distance measure on weighted directed graphs

There is a simple and well-defined distance measure on weighted undirected graphs, namely the least sum of edge weights on any (simple) path between two vertices.

Can one devise a meaningful distance metric for weighted directed graphs? (assume non-negative weights and that the distance must be symmetric and have the triangular property)

-
Could you not do the same thing as with undirected graphs, which gives a non-symmetric metric D, and then symmetrize, i.e. define a metric d by d(x,y) = max{D(x,y), D(y,x)}? – Tom Leinster Feb 3 '10 at 15:58
Yes...I had considered d(x,y) = (D(x,y)+D(y,x))/2 but that just didn't feel right. Did you mean 'min'? If so that seems much more satisfying for edge distance. but...I don't think it'll work for paths. – Mitch Feb 3 '10 at 16:07
Min does not satisfy the triangle inequality, only max does. – domotorp Feb 3 '10 at 16:23
Mitch, I meant max (and agree with domotorp). And yes, I also had it in mind that you could use + to symmetrize, rather than max. It sounds like you have some kind of design criteria in mind for how this distance should behave. Maybe you could add something to the question explaining them? (There's an "edit" button.) – Tom Leinster Feb 3 '10 at 17:24
That min doesn't work but max does is not obvious to me (and I can't seem to think through it). Is there a short counterexample? – Mitch Feb 3 '10 at 20:24

The value of metrics on graphs in combinatorial geometry as an area of pure mathematics are more or less the same as their value in applied mathematics, for instance in direction-finding software in Garmin or Google Maps. In any such setting, the triangle inequality is essential for the metric interpretation, but the symmetry condition $d(x,y) = d(y,x)$ is not. An asymmetric metric captures the idea of one-way distance. You can have perfectly interesting geometry of many kinds without the symmetry condition. For instance, you can study asymmetric Banach norms such that $||\alpha x|| = \alpha ||x||$ for $\alpha > 0$, but $||x|| \ne ||-x||$, or the corresponding types of Finsler manifolds.
On the other hand, if you want to restore symmetry, you can. For instance, $$d'(x,y) = d(x,y) + d(y,x)$$ has a natural interpretation as round-trip distance, which again works equally well for pure and applied purposes. You can also use max, directly, or even min with a modified formula. Namely, you can define $d'$ to be the largest-distance metric such that $$d'(x,y) \le \min(d(x,y),d(y,x))$$ for all $x$ and $y$. All of these have natural interpretations. For instance, the min formula could make sense for streets that are one-way for cars but two-way for bicycles.