Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.22745 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909930968055808 |
|---|---|
| author | Dong, Anqi Taghvaei, Amirhossein Georgiou, Tryphon T. |
| author_facet | Dong, Anqi Taghvaei, Amirhossein Georgiou, Tryphon T. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22745 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A lasso-alternative to Dijkstra's algorithm for identifying short paths in networks Dong, Anqi Taghvaei, Amirhossein Georgiou, Tryphon T. Optimization and Control Distributed, Parallel, and Cluster Computing Social and Information Networks Image and Video Processing 05C38, 05C50, 05C85, 62J07, 90C25 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. |
| title | A lasso-alternative to Dijkstra's algorithm for identifying short paths in networks |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing Social and Information Networks Image and Video Processing 05C38, 05C50, 05C85, 62J07, 90C25 |
| url | https://arxiv.org/abs/2511.22745 |