I am learning graph theory and some concept that I cannot figure it out. A vertex is central in $G$ if its greatest distance from any other vertex is as small as possible. Is there any algorithm to find central vertex in any given graph $G$? Thanks.

Mathematica has a function 


To state more directly what Joseph said, if we know the distance between any two vertices, it is straightforward to first find the eccentricity of $v$, i.e. the maximum distance from $v$ to another vertex. Having done this we simply mark the vertices of lowest eccentricity as being central. To find the distance between every pair of vertices, one can apply the FloydWarshall algorithm for allpairs shortest path, which runs in $O(n^3)$ time. http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm 


I am not sure your definition of centrality is the most useful one; in what's called "network science", the study of largescale graphs, I think some measure of centrality which takes an average rather than a maximum will be more useful. Think for example about a graph which has a vertex $v$, edges $v v_i$ to lots of vertices $v_1, ...,v_N$, and also contains a chain of length say three, $v  w_1  w_2  w_3$. According to your definition, $w_1$ is the center of this graph, but I would say it's $v$. The average distance leads to what's called "closeness centrality". There is also "betweenness centrality", based on the number of shortest paths in the graph that pass through the node divided by the total number of shortest paths; this is trying to measure how useful $v$ is to the rest of the graph. Googling these two phrases will bring up lots of algorithms and further references. Here is a random recent one that seems to have a useful intro: Ranking of Closeness Centrality for LargeScale Social Networks. 


The question should be more specific. It depends what you know about the graph . For a tree you can erase all degree 1 vertices then repeat on the new graph and stop when there are just one or two. The set of centers is invariant under the automorphism group so for a vertex transitive graph every vertex is a center. 

