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

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 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.