Does computing all shortest paths in a simple graph result in a complete graph that follows a metric?

Question

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.

Answer 1

I mean I think you clearly showed the graph $G$ can induce a metric, namely define $d_G(u,v)$ as the shortest path from $u \in V(G)$ to $v \in V(G)$ and you can readily show the three properties you define. The graph $G_c$ is not even needed in this discussion, as far as I can tell. Here is a link to some document that describes a similar claim.