论文标题
最短路径问题的光谱方法
A Spectral Approach to the Shortest Path Problem
论文作者
论文摘要
令$ g =（v，e）$为一个简单的连接图。一个通常对两个顶点$ u，v $之间的短路感兴趣。我们提出了一个频谱算法：构造函数$ ϕ：v \ rightarrow \ mathbb {r} _ {\ geq 0} $ $ $ $ $ $ ϕ = \ arg \ arg \ min_ {f：v \ rightarrow \ rightArrow \ rightArrow \ mathbb {r} \ frac {\ sum _ {（w_1，w_2）\在e} {（f（w_1）-f（w_1）-f（w_2））^2}}}} {\ sum_ {w \ in v} {f（w）^2}}。 $ U- $ th行和列已被删除。我们从点$ v $开始，并构建一条从$ v $到$ u $的路径：在每个步骤中，我们搬到了$ ϕ $最小的邻居。事实证明，该算法可以终止并导致从$ v $到$ u $的短途途径，通常是最短的。该方法的效率是由于部分微分方程中的现象的离散类似物所致，而这些现象尚未得到充分理解。我们证明了树木的最佳性，并讨论了许多开放问题。
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 \mathbb{R}_{\geq 0}$ $$ ϕ= \arg\min_{f:V \rightarrow \mathbb{R} \atop f(u) = 0, f \not\equiv 0} \frac{\sum_{(w_1, w_2) \in E}{(f(w_1)-f(w_2))^2}}{\sum_{w \in 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.
