A spectral approach to the shortest path problem (Q2020688)

For a simple, connected graph \(G\) with vertices \(u,v\in V(G)\), a spectral algorithm is constructed for finding a shortest path from \(v\) to \(u\) in which the Laplacian matrix is used. The efficiency of this method is due to a discrete analogue of a not well understood phenomenon in partial differential equations. Moreover, the optimality of this method is proved for trees, and some open problems are discussed.