Distance between vertices in a directed graph

311 Views Asked by At

We know that an unweighted undirected graph $G = (V(G), E(G))$ with the geodesic distance $d_{G}$ is a metric space (if we allow $d_{G}$ to attain $\infty$ or if $G$ is connected)(we'd better say an extended metric space) and if $G$ is a weighted undirected graph then it will be a pseudometric space with $d_{G}$. Now, if the graph is directed is $d_{G}$ still some special function? I mean something similar to a metric, pseudometric, etc. Of course, then $d_{G}$ will be a function from $|V(G)|$, not $|V(G)| \times |V(G)|$. Can we modify $d_{G}$ to get us a good distance function from $|V(G)| \times |V(G)|$ to $\mathbb{R^{+}}$?