We consider the classical single-source shortest path problem in directed weighted graphs. Eppstein proved recently an \(\Omega(n^{3})\) lower bound for oblivious algorithms that use relaxation operations to update the tentative distances from the source vertex. We generalize this result by extending this \(\Omega(n^{3})\) lower bound to adaptive algorithms that, in addition to relaxations, can perform queries involving some simple types of linear inequalities between edge weights and tentative distances. Our model captures as a special case the operations on tentative distances used by Dijkstra’s algorithm.

We study search trees with 2-way comparisons ( 2wcst ’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons ( 3wcst ’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. In 2002, Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ − is the largest ratio that forces the less-than test, and λ + is the smallest ratio that admits the equal-to test. They determined that λ − = 1 4 , but for the higher threshold they only showed that λ + ∈ [ 3 7 , 4 9 ] . We give the tight bound for the higher threshold, by proving that in fact λ + = 3 7 .