Return to Answer

###Update: This solution is not correct.

The solution is unfortunately only true (and straightforward) for trees! Finding the diameter of a tree does not even need this. Here is a counterexample for graphs (diameter is 4, the algorithm returns 3 if you pick this $v$):

If the graph is directed this is rather complex, here is some paper claiming faster results in the dense case than using algorithms for all-pairs shortest paths.

However my main point is about the case the graph is not directed and with non-negative weigths, I heard of a nice trick several times:

1. Pick a vertex $v$
2. Find $u$ such that $d(v,u)$ is maximum
3. Find $w$ such that $d(u,w)$ is maximum
4. Return $d(u,w)$

Its complexity is the same as two successive breadth first searches¹, that is $O(|E|)$ if the graph is connected².

It seemed folklore but right now, I'm still struggling to get a reference or to prove its correction. I'll update when I'll achieve one of these goals. It seems so simple I post my answer right now, maybe someone will get it faster.

¹ if the graph is weighted, wikipedia seems to say $O(|E|+|V|\log|V|)$ but I am only sure about $O(|E|\log|V|)$.

² If the graph is not connected you get $O(|V|+|E|)$ but you may have to add $O(α(|V|))$ to pick one element from each connected component. I'm not sure if this is necessary and anyway, you may decide that the diameter is infinite in this case.

Update:

This solution is not correct.

The solution is unfortunately only true (and straightforward) for trees! Finding the diameter of a tree does not even need this. Here is a counterexample for graphs (diameter is 4, the algorithm returns 3 if you pick this $v$):

If the graph is directed this is rather complex, here is some paper claiming faster results in the dense case than using algorithms for all-pairs shortest paths.

However my main point is about the case the graph is not directed and with non-negative weigths, I heard of a nice trick several times:

1. Pick a vertex $v$
2. Find $u$ such that $d(v,u)$ is maximum
3. Find $w$ such that $d(u,w)$ is maximum
4. Return $d(u,w)$

Its complexity is the same as two successive breadth first searches¹, that is $O(|E|)$ if the graph is connected².

It seemed folklore but right now, I'm still struggling to get a reference or to prove its correction. I'll update when I'll achieve one of these goals. It seems so simple I post my answer right now, maybe someone will get it faster.

¹ if the graph is weighted, wikipedia seems to say $O(|E|+|V|\log|V|)$ but I am only sure about $O(|E|\log|V|)$.

² If the graph is not connected you get $O(|V|+|E|)$ but you may have to add $O(α(|V|))$ to pick one element from each connected component. I'm not sure if this is necessary and anyway, you may decide that the diameter is infinite in this case.

If the graph is directed this is rather complex, here is some paper claiming faster results in the dense case than using algorithms for all-pairs shortest paths.

However my main point is about the case the graph is not directed and with non-negative weigths, I heard of a nice trick several times:

1. Pick a vertex $v$
2. Find $u$ such that $d(v,u)$ is maximum
3. Find $w$ such that $d(u,w)$ is maximum
4. Return $d(u,w)$

Its complexity is the same as two successive breadth first searches¹, that is $O(|E|)$ if the graph is connected².

It seemed folklore but right now, I'm still struggling to get a reference or to prove its correction. I'll update when I'll achieve one of these goals. It seems so simple I post my answer right now, maybe someone will get it faster.

¹ if the graph is weighted, wikipedia seems to say $O(|E|+|V|\log|V|)$ but I am only sure about $O(|E|\log|V|)$.

² If the graph is not connected you get $O(|V|+|E|)$ but you may have to add $O(α(|V|))$ to pick one element from each connected component. I'm not sure if this is necessary and anyway, you may decide that the diameter is infinite in this case.

EDIT: my bad, this unfortunately only true (and straightforward) for trees! Finding the diameter of a tree does not even need this. Here is a counterexample for graphs (diameter is 4, the algorithm returns 3 if you pick this $v$):

###Update: This solution is not correct.

The solution is unfortunately only true (and straightforward) for trees! Finding the diameter of a tree does not even need this. Here is a counterexample for graphs (diameter is 4, the algorithm returns 3 if you pick this $v$):

If the graph is directed this is rather complex, here is some paper claiming faster results in the dense case than using algorithms for all-pairs shortest paths.

However my main point is about the case the graph is not directed and with non-negative weigths, I heard of a nice trick several times:

1. Pick a vertex $v$
2. Find $u$ such that $d(v,u)$ is maximum
3. Find $w$ such that $d(u,w)$ is maximum
4. Return $d(u,w)$

Its complexity is the same as two successive breadth first searches¹, that is $O(|E|)$ if the graph is connected².

It seemed folklore but right now, I'm still struggling to get a reference or to prove its correction. I'll update when I'll achieve one of these goals. It seems so simple I post my answer right now, maybe someone will get it faster.

¹ if the graph is weighted, wikipedia seems to say $O(|E|+|V|\log|V|)$ but I am only sure about $O(|E|\log|V|)$.

² If the graph is not connected you get $O(|V|+|E|)$ but you may have to add $O(α(|V|))$ to pick one element from each connected component. I'm not sure if this is necessary and anyway, you may decide that the diameter is infinite in this case.

If the graph is directed this is rather complex, here is some paper claiming faster results in the dense case than using algorithms for all-pairs shortest paths.

However my main point is about the case the graph is not directed and with non-negative weigths, I heard of a nice trick several times:

1. Pick a vertex $v$
2. Find $u$ such that $d(v,u)$ is maximum
3. Find $w$ such that $d(u,w)$ is maximum
4. Return $d(u,w)$

Its complexity is the same as two successive breadth first searches¹, that is $O(|E|)$ if the graph is connected².

It seemed folklore but right now, I'm still struggling to get a reference or to prove its correction. I'll update when I'll achieve one of these goals. It seems so simple I post my answer right now, maybe someone will get it faster.

¹ if the graph is weighted, wikipedia seems to say $O(|E|+|V|\log|V|)$ but I am only sure about $O(|E|\log|V|)$.

² If the graph is not connected you get $O(|V|+|E|)$ but you may have to add $O(α(|V|))$ to pick one element from each connected component. I'm not sure if this is necessary and anyway, you may decide that the diameter is infinite in this case.

If the graph is directed this is rather complex, here is some paper claiming faster results in the dense case than using algorithms for all-pairs shortest paths.

However my main point is about the case the graph is not directed and with non-negative weigths, I heard of a nice trick several times:

1. Pick a vertex $v$
2. Find $u$ such that $d(v,u)$ is maximum
3. Find $w$ such that $d(u,w)$ is maximum
4. Return $d(u,w)$

Its complexity is the same as two successive breadth first searches¹, that is $O(|E|)$ if the graph is connected².

It seemed folklore but right now, I'm still struggling to get a reference or to prove its correction. I'll update when I'll achieve one of these goals. It seems so simple I post my answer right now, maybe someone will get it faster.

¹ if the graph is weighted, wikipedia seems to say $O(|E|+|V|\log|V|)$ but I am only sure about $O(|E|\log|V|)$.

² If the graph is not connected you get $O(|V|+|E|)$ but you may have to add $O(α(|V|))$ to pick one element from each connected component. I'm not sure if this is necessary and anyway, you may decide that the diameter is infinite in this case.

EDIT: my bad, this unfortunately only true (and straightforward) for trees! Finding the diameter of a tree does not even need this. Here is a counterexample for graphs (diameter is 4, the algorithm returns 3 if you pick this $v$):