Dijkstra's algorithm will give you the shortest path from a given node to all other nodes in the connected graph. One way to get your average is to iterate through each node of the graph, running Dijkstra's algorithm to get the shortest distance from that node to each of the others, and taking the average of paths starting from that node. Accumulate the "average of paths starting from current node" as you iterate. Divide by number of nodes when you finish iterating.
This is a brute force approach, and will calculate each distance twice, but it should give you the correct average.