A Spectral Approach to the Shortest Path Problem

Abstract Let G = ( V , E ) be a simple, connected graph. One is often interested in a short path between two vertices u , v ∈ V . We propose a spectral algorithm: construct the function ϕ : V → R ≥ 0 ϕ = arg ⁡ min f : V → R f ( u ) = 0 , f ≢ 0 ⁡ ∑ ( w 1 , w 2 ) ∈ E ( f ( w 1 ) − f ( w 2 ) ) 2 ∑ w ∈ V f ( 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.