Diameter of a graph

Another measure for the structure of a graph is its diameter. Diameter δ is an index measuring the topological length or extent of a graph by counting the number of edges in the shortest path between the most distant vertices. It is:

where s(i, j) is the number of edges in the shortest path from vertex i to vertex j. With this formula, first, all the shortest paths between all the vertices are searched; then, the longest path is chosen. This measure therefore describes the longest shortest path between two random vertices of a graph.

The first two figures in graph A show possible paths but not the shortest paths. The third figure and figure B show the longest shortest path.

In addition to the purely topological application, actual track lenths or any other weight (e.g. travel time) can be assigned to the edges. This suggests a more complex measurement based on the metric of the network. The resulting index is π = mT/mδ, where mT is the total mileage of the network and mδ is the total mileage of the network's diameter. The higher π is, the denser the network.