0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.