用lasso方法重解最短路径问题，可高效应对网络拓扑变化。
A lasso-alternative to Dijkstra's algorithm for identifying short paths in networks
- 将最短路径建模为l1正则化回归问题，借助LARS求解。
- 在双向Dijkstra算法框架下，实现路径搜索与拓扑更新的统一优化。
- 适合需频繁更新图结构的动态网络场景，如交通调度、实时路由。
我们重新审视图中两点间最短路径问题，将其建模为ℓ₁-正则化回归——最小绝对收缩与选择算子（lasso）。通过数值实现该lasso形式化，采用LARS算法，与经典的双向Dijkstra算法建立联系。本方法的优势在于可应用交替方向乘子法（ADMM）求解，并能相对高效地处理图的拓扑变更，适用于需要动态更新路径的复杂网络系统。
原文摘要 · Abstract (English)
We revisit the problem of finding the shortest path between two selected vertices of a graph and formulate this as an $\ell_1$-regularized regression -- Least Absolute Shrinkage and Selection Operator (lasso). We draw connections between a numerical implementation of this lasso-formulation, using the so-called LARS algorithm, and a more established algorithm known as the bi-directional Dijkstra. Appealing features of our formulation include the applicability of the Alternating Direction of Multiplier Method (ADMM) to the problem to identify short paths, and a relatively efficient update to topological changes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。