Information Bounds Are Weak in the Shortest Distance Problem
Ronald Graham, Andrew Chi-Chih Yao, F. Frances Yao · Journal of the ACM · 1980
ASSTRACT. In the all-pair shortest distance problem, one computes the matrix D = (du), where dq is the minimum weighted length of any path from vertex i to vertexj in a directed complete graph with a weight on each edge. In all the known algorithms, a shortest path p, ~ achieving di./is also implicitly computed. In fact, logs(f (n)) is an information-theoretic lower bound, wheref(n) is the total number of distinct patterns (Po) for n-vertex graphs. As f(n) potentially can be as large as 2":', it would appear possible that a nontrivial lower bound can be derived this way in the decision tree model. The characterization and enumeration of realizable patterns is studied, and it is shown thatf(n) 0 and the triangle inequalities d~j + dik> d,k, has at most C" ' faces of all dimensions, thus resolving an open question in a similar information bound approach to the shortest distance problem.