The shortest path from some vertex v to some other vertex w in edge weighted graph G(V, E, W) is the path from v to w with the minimum distance. Shortest path problem is defined to be the problem of finding the shortest path in G(V, E, W). In this paper a different version of shortest path problem is considered. The length of a path is defined to be the number of edges in the path here. The problem considered in this paper is the average length of the shortest paths in G(V, E, W) with non-negative edge distances. It is proved that the upper bound of the average length of a shortest path in G(V, E, W) is O(log N) when G(V, E, W) is a complete graph with N vertices and the distances associated to the edges in G are identically distributed on [0, 1] mutually independent random variables. A concept called shortest path spanning tree that is used in proving the upper bound is also given. Combining with an appropiate data structure, the upper bound proved in this paper implies that there is a shortest path enquiry system with response time O(log N) at the cost of O(N2) space requirement.