# A Spectral Approach to the Shortest Path Problem

arXiv: https://arxiv.org/abs/2004.01163 · HTML: https://mlsanity.com/paper/2004.01163/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Apr 2020.

## Built on by (most cited first, 1 of 1)

- [Bridging Local and Global Knowledge: Cascaded Mixture-of-Experts Learning for Near-Shortest Path Routing](https://mlsanity.com/paper/2603.15541/) (2026)

## Abstract (arXiv)

Let G=(V,E) be a simple, connected graph. One is often interested in a short path between two vertices u,v. We propose a spectral algorithm: construct the function φ:V rightarrow ℝ≥ 0  φ = argminf:V rightarrow ℝ atop f(u) = 0, f notequiv 0 fracsum(w1, w2) ∈ E(f(w1)-f(w2))2sumw ∈ Vf(w)2. φ can also be understood as the smallest eigenvector of the Laplacian Matrix L=D-A after the u-th row and column have been removed. We start in the point v and construct a path from v to u: at each step, we move to the neighbor for which φ is the smallest. This algorithm provably terminates and results in a short path from v to u, often the shortest. The efficiency of this method is due to a discrete analogue of a phenomenon in Partial Differential Equations that is not well understood. We prove optimality for trees and discuss a number of open questions.