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

Improve this question
$\endgroup$
2
  • 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
    Commented Apr 7, 2017 at 15:51
  • $\begingroup$ Ah, that was so dumb of me, I didn't even think about that. Thank you! $\endgroup$
    – User1915
    Commented Apr 7, 2017 at 16:15

1 Answer 1

Reset to default
3
$\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.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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