# How to show that triangle inequality holds for normalized shortest path in graph?

I have two sets of nodes A and B with size L and M on graph.

For every nodes in set A, I'm computing minimum length shortest path to nodes in set B(at the end for each node, I have just one minimum length shortest path).Then I sum it up (summing up for the nodes in set A) and normalize it by the size of set A

How can I show that this is distance metric and satisfy triangle inequality? Ofcourse I know that distance from A->B might not equal to B->A, but can I set it to equal by definition ? I mean, I want to set dist(A-B)=dist(B-A)

• I don't think it is; for one thing, it's not symmetric. If your graph looks like a1 a2 b1 ............ b2 with $A = \{a_1, a_2\}$ and $B = \{b_1, b_2\}$, then the average distance from a node in $A$ to $B$ is $1.5$, but (because of $b_2$) the average distance from a node in $B$ to $A$ is huge. – Misha Lavrov Oct 24 '17 at 16:23
• Well, suppose I take the final distance as average of distance in both direction. then , distance from A->B will be the same as B->A. Also is it wrong that, by defination, I set distance of A->B equal to B->A ? – user2806363 Oct 24 '17 at 17:16
• It's not wrong to do that, but then you're using a definition that's different from the one in your question, which doesn't do this. – Misha Lavrov Oct 24 '17 at 17:22
• Sounds good. Do you know how can I prove that triangle inequality holds for this case ? – user2806363 Oct 24 '17 at 17:31

## 1 Answer

As I pointed out in the comment, the original definition is not symmetric. There are several ways to fix this, but not all of them will satisfy the triangle inequality.

Let $D(A,B)$ be the function you've defined above: the minimum distance from $a$ to $B$, averaged over all $a \in A$. We could try replacing this with

• $\min\{D(A,B), D(B,A)\}$ or
• $\frac12(D(A,B) + D(B,A))$ or
• $\max\{D(A,B), D(B,A)\}$

but none of these satisfy the triangle inequality. Consider a path on $6$ vertices $a_1, a_2, b_1, b_2, c_1, c_2$ in that order, and let $A =\{a_1, a_2\}$, $B = \{b_1, b_2\}$, $C = \{c_1, c_2\}$. Then $D(A,B) = D(B,A) = 1.5$, so any approach to "fixing the symmetry" would leave the distance between them at $1.5$. Similarly, $D(B,C) = D(C,B) = 1.5$. But $D(A,C) = D(C,A) = 3.5$, and $3.5 > 1.5 + 1.5$, so the triangle inequality is not satisfied.

What does work is defining the distance between vertex sets $A$ and $B$ to be the graph distance $d(a,b)$ averaged over all pairs $(a,b) \in A \times B$. Let $D^*(A,B)$ be this average.

This satisfies the triangle inequality: if $A, B, C$ are any vertex sets, then by the graph distance triangle inequality we have $d(a,b) + d(b,c) \ge d(a,c)$ for any $a\in A$, $b\in B$, and $c\in C$. Therefore $$\frac{1}{|A||B||C|}\sum_{a \in A}\sum_{b\in B}\sum_{c \in C}(d(a,b)+d(b,c)) \ge \frac{1}{|A||B||C|}\sum_{a \in A}\sum_{b\in B}\sum_{c \in C} d(a,c)$$ and this simplifies to $$D^*(A,B) + D^*(B,C) \ge D^*(A,C).$$

It does still have the problem that $D^*(A,A) \ne 0$, so it's still not quite a metric...

• Good, but I think (1-cor(Dist)) would fix it. Don't think so ? – user2806363 Oct 24 '17 at 19:24
• Could you elaborate? – Misha Lavrov Oct 24 '17 at 19:30