0
$\begingroup$

I used networkx to find the diameter of a graph that I have. It gave a diameter of 4. However, I found that between two particular nodes, using networkx's shortest path function, the path length is 5. I also coded dijkstra's algorithm and BFS from scratch and both returned a shortest path length of 5 too.

Is anything wrong with this? Isn't the diameter of a graph the longest shortest path?

This is what I'm using: http://vlado.fmf.uni-lj.si/pub/networks/data/Erdos/Erdos02.net

$\endgroup$
  • 2
    $\begingroup$ Perhaps you're confusing the number of vertices in the shortest path with the length of the path? If the shortest path contains 5 vertices, then the path length (and distance) between those vertices is 4 $\endgroup$ – Ariel Apr 7 '17 at 15:51
  • $\begingroup$ Ah, that was so dumb of me, I didn't even think about that. Thank you! $\endgroup$ – User1915 Apr 7 '17 at 16:15
2
$\begingroup$

The diameter of a graph is, by definition, the length of the longest shortest path, i.e.,

$$\mathrm{diam}(G) = \max_{x,y\in V(G)} \min\, \{\mathrm{len}(P)\mid P\text{ is a path from }x\text{ to }y\}\,.$$

But remember that the length of a path is the number of edges it contains, not the number of vertices. (That is, a single edge is a path of length 1, not 2.)

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