Two directions in algorithms and complexity involve: (1) classifying which optimization problems can be solved in polynomial time, and (2) understanding which computational problems are hard to solve \emph{on average} in addition to the worst case. For many average-case problems, there does not currently exist strong evidence via reductions that they are hard. However, we can still attempt to predict their polynomial time tractability by proving lower bounds against restricted classes of algorithms. Geometric approaches to predicting tractability typically study the \emph{optimization landscape}. For optimization problems with random objectives or constraints, ideas originating in statistical physics suggest we should study the \emph{overlap} between approximately-optimal solutions. Formally, properties of \emph{Gibbs measures} and the \emph{Franz–Parisi potential} imply lower bounds against natural local search algorithms, such as Langevin dynamics. A related theory, the \emph{Overlap Gap Property (OGP)}, proves rigorous lower bounds against classes of algorithms which are stable functions of their input. A remarkable recent work of Li and Schramm [COLT 2025] showed that the shortest path problem in random graphs, which is polynomial-time tractable, admits lower bounds against a class of stable algorithms via the OGP. We further investigate and find that: (1) via the OGP and FPP, we can show stable algorithms and natural MCMC chains fail in the optimization landscape of shortest paths, but (2) stable algorithms and local search succeed in the optimization landscape for shortest path \emph{trees}, which agrees with OGP and FPP predictions.