The authors discuss the all-pairs minimum average weighted length path problem which can be stated as follows. Suppose they are given a network N=(V,A) in which each arc(i,j)∈A, has two weights, representing say length and journey time. The length of any path P* in N is defined to be sum of the lengths of the arcs of P*. The journey time of P* is defined analogously. It is required to find a path P*, between each pair of nodes in V such that the ratio of the length of P* to the journey time of P* is minimized. This problem is shown to be NP-hard. An algorithm is developed which is pseudo-polynomial for the special case in which N does not contain a so-called ‘tadpole’-a structure analogous to a negative cycle in the shortest path problem. If, in addition, the times of traversal are equal, then the algorithm is polynomial. The authors further show that the detection of a tadpole in a general network is an NP-complete problem.
