Outperforming Dijkstra on Sparse Graphs: The Lightning Network Use Case
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914041124880384 |
|---|---|
| author | Valko, Danila Paranjpe, Rohan Gómez, Jorge Marx |
| author_facet | Valko, Danila Paranjpe, Rohan Gómez, Jorge Marx |
| contents | Efficient routing is critical for payment channel networks (PCNs) such as the Lightning Network (LN), where most clients currently rely on Dijkstra-based algorithms for payment pathfinding. While Dijkstra's algorithm has long been regarded as optimal on sparse graphs, recent theoretical work challenges this view. The new Bounded Multi-Source Shortest Path (BMSSP) algorithm by Duan et al. theoretically achieves $O(m~log^{2/3}~n)$ runtime, which is asymptotically faster than Dijkstra's $O(m + n~log~n)$ on sparse directed graphs. In this paper, we implement BMSSP on Rust and compare its performance against Dijkstra's using real LN topology data. Our evaluation, based on multiple randomized trials and statistical tests, shows that current implementations of BMSSP do not significantly outperform Dijkstra's in practice, and speedups are smaller than what theory predicts, possibly due to implementation and constant factor overheads. These results provide the first empirical evidence of BMSSP's potential to accelerate LN routing and inform future optimizations of PCN pathfinding algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_13448 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Outperforming Dijkstra on Sparse Graphs: The Lightning Network Use Case Valko, Danila Paranjpe, Rohan Gómez, Jorge Marx Performance Data Structures and Algorithms Social and Information Networks Efficient routing is critical for payment channel networks (PCNs) such as the Lightning Network (LN), where most clients currently rely on Dijkstra-based algorithms for payment pathfinding. While Dijkstra's algorithm has long been regarded as optimal on sparse graphs, recent theoretical work challenges this view. The new Bounded Multi-Source Shortest Path (BMSSP) algorithm by Duan et al. theoretically achieves $O(m~log^{2/3}~n)$ runtime, which is asymptotically faster than Dijkstra's $O(m + n~log~n)$ on sparse directed graphs. In this paper, we implement BMSSP on Rust and compare its performance against Dijkstra's using real LN topology data. Our evaluation, based on multiple randomized trials and statistical tests, shows that current implementations of BMSSP do not significantly outperform Dijkstra's in practice, and speedups are smaller than what theory predicts, possibly due to implementation and constant factor overheads. These results provide the first empirical evidence of BMSSP's potential to accelerate LN routing and inform future optimizations of PCN pathfinding algorithms. |
| title | Outperforming Dijkstra on Sparse Graphs: The Lightning Network Use Case |
| topic | Performance Data Structures and Algorithms Social and Information Networks |
| url | https://arxiv.org/abs/2509.13448 |