Negative-Weight Single-Source Shortest Paths in Near-Linear Time.
In this research article, the authors present a simple combinatorial algorithm that reduces running time to near-linear to address the single-source shortest paths problem. The authors present two questions-- including can the algorithm perform without complex machinery-- and five theorems--that dea...
| Publicado en: | Communications of the ACM Vol. 68; no. 2; pp. 87 - 95 |
|---|---|
| Autores principales: | , , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Feb2025
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| Sumario: | In this research article, the authors present a simple combinatorial algorithm that reduces running time to near-linear to address the single-source shortest paths problem. The authors present two questions-- including can the algorithm perform without complex machinery-- and five theorems--that deal with negative-weight cycle-- in this research and evaluate two algorithms, ScaleDown and the simpler SPMain, in regards to these. Topics include price functions and low-diameter decomposition. |
|---|