A Bottom-Up Algorithm for Negative-Weight SSSP with Integrated Negative Cycle Finding
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913590259220480 |
|---|---|
| author | Li, Jason Mowry, Connor |
| author_facet | Li, Jason Mowry, Connor |
| contents | We present a simplified algorithm for solving the Negative-Weight Single-Source Shortest Paths (SSSP) problem, focusing on enhancing clarity and practicality over prior methods. Our algorithm uses graph diameter as a recursive parameter, offering greater robustness to the properties of the decomposed graph compared to earlier approaches. Additionally, we fully integrate negative-weight cycle finding into the algorithm by augmenting the Bellman-Ford/Dijkstra hybrid, eliminating the need for a separate cycle-finding procedure found in prior methods. Although the algorithm achieves no theoretical efficiency gains, it simplifies negative cycle finding and emphasizes design simplicity, making it more accessible for implementation and analysis. This work highlights the importance of robust parameterization and algorithmic simplicity in addressing the challenges of Negative-Weight SSSP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19449 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Bottom-Up Algorithm for Negative-Weight SSSP with Integrated Negative Cycle Finding Li, Jason Mowry, Connor Data Structures and Algorithms We present a simplified algorithm for solving the Negative-Weight Single-Source Shortest Paths (SSSP) problem, focusing on enhancing clarity and practicality over prior methods. Our algorithm uses graph diameter as a recursive parameter, offering greater robustness to the properties of the decomposed graph compared to earlier approaches. Additionally, we fully integrate negative-weight cycle finding into the algorithm by augmenting the Bellman-Ford/Dijkstra hybrid, eliminating the need for a separate cycle-finding procedure found in prior methods. Although the algorithm achieves no theoretical efficiency gains, it simplifies negative cycle finding and emphasizes design simplicity, making it more accessible for implementation and analysis. This work highlights the importance of robust parameterization and algorithmic simplicity in addressing the challenges of Negative-Weight SSSP. |
| title | A Bottom-Up Algorithm for Negative-Weight SSSP with Integrated Negative Cycle Finding |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.19449 |