A spectral approach to the shortest path problem

DOI10.1016/J.LAA.2021.02.013zbMATH Open1475.05058arXiv2004.01163OpenAlexW3132950972MaRDI QIDQ2020688FDOQ2020688

Authors: Stefan Steinerberger 

Publication date: 24 April 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: 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 $phi:Vightarrowmathbb{R}_{geq0}$ ${\displaystyle }$ phi = argmin_{f:V ightarrow mathbb{R} atop f(u) = 0, f otequiv 0} frac{sum_{(w_1, w_2) in E}{(f(w_1)-f(w_2))^2}}{sum_{w in V}{f(w)^2}}.${\displaystyle }$ $phi$ 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 $phi$ 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.

Full work available at URL: https://arxiv.org/abs/2004.01163

Recommendations

• A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem
• Shortest paths in Euclidean graphs
• Computing the shortest path: \(A^\ast\) search meets graph theory
• A simpler and more efficient algorithm for the next-to-shortest path problem
• scientific article; zbMATH DE number 1875419

zbMATH Keywords

shortest path problemspectral theoryhot spots

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Distance in graphs (05C12)

Cites Work

• Diffusion maps
• A note on two problems in connexion with graphs
• Title not available (Why is that?)
• On a routing problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• Title not available (Why is that?)
• A Theorem on Boolean Matrices
• Rearrangements and convexity of level sets in PDE
• Nodal sets of eigenfunctions on Riemannian manifolds
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• Spectral sparsification of graphs
• Nodal sets of solutions of elliptic and parabolic equations
• Nodal Sets for Eigenfunctions of the Laplacian On Surfaces
• Title not available (Why is that?)
• Efficient Algorithms for Shortest Paths in Sparse Networks
• A Nearly-m log n Time Solver for SDD Linear Systems
• Nodal sets for solutions of elliptic equations
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• A new approach to all-pairs shortest paths on real-weighted graphs
• Title not available (Why is that?)
• On the ``hot spots conjecture of J. Rauch
• Geodesic distance and curves through isotropic and anisotropic heat equations on images and surfaces
• Scaling coupling of reflecting Brownian motions and the hot spots problem
• Solutions of the Shortest-Route Problem—A Review
• Isoperimetric Inequalities and Their Applications
• Diffusion processes in a small time interval
• Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces
• Diffusion processes in a small time interval
• Neumann domains on graphs and manifolds
• Locating the first nodal linein the Neumann problem
• Faster all-pairs shortest paths via circuit complexity
• Shortest paths algorithms: Theory and experimental evaluation
• Computing geodesic paths on manifolds
• Undirected single-source shortest paths with positive integer weights in linear time
• Distance Functions and Geodesics on Submanifolds of $\R^d$ and Point Clouds
• On the nodal line of the second eigenfunction of the Laplacian in \(\mathbb{R}^ 2\)
• On nodal lines of Neumann eigenfunctions
• Title not available (Why is that?)
• Nodal lines of eigenfunctions of the fixed membrane problem in general convex domains
• Nodal sets of eigenfunctions on Riemann surfaces
• Asymptotics of the first nodal line of a convex domain
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• On Neumann eigenfunctions in lip domains
• The “hot spots” conjecture for domains with two axes of symmetry
• Closed Nodal Lines and Interior Hot Spots of the Second Eigenfunctions of the Laplacian on Surfaces
• A counterexample to the ``hot spots conjecture
• The ``hot spots conjecture for a certain class of planar convex domains
• The hot spots problem in planar domains with on hole
• Path planning with divergence-based distance functions
• Fiber Brownian motion and the ``hot spots problem
• An inequality for potentials and the 'hot-spots' conjecture
• A variational approach to the consistency of spectral clustering
• The size of the first eigenfunction of a convex planar domain
• On the Location of Maxima of Solutions of Schrödinger's Equation
• A planar convex domain with many isolated ``hot spots on the boundary
• Euclidean triangles have no hot spots
• Hot spots in convex domains are in the tips (up to an inradius)
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• An O(m log log D) algorithm for shortest paths
• Hamilton Circuits of Convex Trivalent Polyhedra (Up to 18 Vertices)
• Properly-weighted graph Laplacian for semi-supervised learning
• The game theoretic \(p\)-Laplacian and semi-supervised learning with few labels
• Schur reduction of trees and extremal entries of the Fiedler vector
• Distance transform gradient density estimation using the stationary phase approximation
• A continuum limit for the PageRank algorithm

Cited In (4)

• Short Normal Paths and Spectral Variation
• Connected components and minimum paths
• Title not available (Why is that?)
• Extreme values of the Fiedler vector on trees

Uses Software

• Algorithm 97

This page was built for publication: A spectral approach to the shortest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2020688)