Search code examples
network-programminggraphpathaveragevertices

Average path length of a network graph?

I have this network graph:

enter image description here

I created a distance matrix based on each vertex:

enter image description here

What i want to do now is to find the "average path length" of the network graph above, but the definition says "the average length of shortest path between any two vertices". I couldn't work my head around that definition and was wondering if anyone could help me out on this.

Solution

  • "-the shortest path between two vertices" refers to the minimum number of steps or smallest possible sum of edge weights (only 1 for this case of an unweighted graph) from a location to a destination vertex.

    The average is calculated from all possible paths such as A to B and B to A, however we don't consider A to A as the graph does not illustrate any recursive paths.

    Therefore to calculate the average by summing all the path values from your table and dividing by the number of paths (excluding recursive paths such as A to A).

    41/30 = 1.4 (rounded from 1.36)