I have a simple graph $G=(V,E)$ that is not necessarily a complete graph. If I compute the shortest distance between every pair of vertices (let say with Floyd-Warshall algorithm) I get a complete graph $G_c=(V,E_c)$. Considering that the distance between two vertices in a simple graph is the number of edges in its shortest path, the following holds for $G_c$:
- $\forall v \in V , d(v,v) = 0$
- $\forall u,v \in V , d(u,v)=d(v,u)$
- $\forall u,v,w \in V , d(u,v) \le d(u,w) + d(w,v)$
Namely, graph $G_c$ respects a metric.
Intuitively, I can see why this is true. But I haven't found a reference for such a result. Could you provide me with one? or maybe I am wrong?
I really appreciate any help you can provide.