Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.shortest_paths.generic.average_shortest_path_length

average_shortest_path_length(G, weight=None, method='dijkstra')[source]

Return the average shortest path length.

The average shortest path length is

\[a =\sum_{s,t \in V} \frac{d(s, t)}{n(n-1)}\]

where V is the set of nodes in G, d(s, t) is the shortest path from s to t, and n is the number of nodes in G.

Parameters:
  • G (NetworkX graph)
  • weight (None or string, optional (default = None)) – If None, every edge has weight/distance/cost 1. If a string, use this edge attribute as the edge weight. Any edge attribute not present defaults to 1.
  • method (string, optional (default = ‘dijkstra’)) – The algorithm to use to compute the path lengths. Supported options: ‘dijkstra’, ‘bellman-ford’. Other inputs produce a ValueError. If weight is None, unweighted graph methods are used, and this suggestion is ignored.
Raises:
  • NetworkXPointlessConcept – If G is the null graph (that is, the graph on zero nodes).
  • NetworkXError – If G is not connected (or not weakly connected, in the case of a directed graph).
  • ValueError – If method is not among the supported options.

Examples

>>> G = nx.path_graph(5)
>>> nx.average_shortest_path_length(G)
2.0

For disconnected graphs, you can compute the average shortest path length for each component

>>> G = nx.Graph([(1, 2), (3, 4)])
>>> for C in nx.connected_component_subgraphs(G):
...     print(nx.average_shortest_path_length(C))
1.0
1.0