Outperforming Dijkstra on Sparse Graphs: The Lightning Network Use Case Article Swipe
Rohan Paranjpe
,
Jorge Marx Gómez
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2509.13448
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2509.13448
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.
Related Topics
Concepts
No concepts available.
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2509.13448
- https://arxiv.org/pdf/2509.13448
- OA Status
- green
- OpenAlex ID
- https://openalex.org/W4416259462
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4416259462Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2509.13448Digital Object Identifier
- Title
-
Outperforming Dijkstra on Sparse Graphs: The Lightning Network Use CaseWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-09-16Full publication date if available
- Authors
-
Rohan Paranjpe, Jorge Marx GómezList of authors in order
- Landing page
-
https://arxiv.org/abs/2509.13448Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2509.13448Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2509.13448Direct OA link when available
- Cited by
-
0Total citation count in OpenAlex
Full payload
| id | https://openalex.org/W4416259462 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2509.13448 |
| ids.doi | https://doi.org/10.48550/arxiv.2509.13448 |
| ids.openalex | https://openalex.org/W4416259462 |
| fwci | |
| type | preprint |
| title | Outperforming Dijkstra on Sparse Graphs: The Lightning Network Use Case |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2509.13448 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2509.13448 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2509.13448 |
| locations[1].id | doi:10.48550/arxiv.2509.13448 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2509.13448 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5120355112 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Rohan Paranjpe |
| authorships[0].author_position | last |
| authorships[0].raw_author_name | Paranjpe, Rohan |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5027635656 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-7833-7549 |
| authorships[1].author.display_name | Jorge Marx Gómez |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Gómez, Jorge Marx |
| authorships[1].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2509.13448 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Outperforming Dijkstra on Sparse Graphs: The Lightning Network Use Case |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-28T09:36:10.625607 |
| primary_topic | |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2509.13448 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2509.13448 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2509.13448 |
| primary_location.id | pmh:oai:arXiv.org:2509.13448 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2509.13448 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2509.13448 |
| publication_date | 2025-09-16 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.+ | 67 |
| abstract_inverted_index.In | 73 |
| abstract_inverted_index.LN | 89, 143 |
| abstract_inverted_index.as | 10, 33 |
| abstract_inverted_index.by | 52 |
| abstract_inverted_index.do | 108 |
| abstract_inverted_index.et | 54 |
| abstract_inverted_index.in | 113 |
| abstract_inverted_index.is | 2, 61 |
| abstract_inverted_index.of | 106, 138, 149 |
| abstract_inverted_index.on | 20, 35, 69, 79, 95 |
| abstract_inverted_index.to | 125, 141 |
| abstract_inverted_index.we | 76 |
| abstract_inverted_index.Our | 92 |
| abstract_inverted_index.PCN | 150 |
| abstract_inverted_index.The | 44 |
| abstract_inverted_index.al. | 55 |
| abstract_inverted_index.and | 81, 99, 115, 127, 145 |
| abstract_inverted_index.are | 117 |
| abstract_inverted_index.due | 124 |
| abstract_inverted_index.for | 4, 23 |
| abstract_inverted_index.has | 29 |
| abstract_inverted_index.its | 83 |
| abstract_inverted_index.new | 45 |
| abstract_inverted_index.not | 109 |
| abstract_inverted_index.the | 11, 134 |
| abstract_inverted_index.$O(m | 66 |
| abstract_inverted_index.Duan | 53 |
| abstract_inverted_index.Path | 49 |
| abstract_inverted_index.Rust | 80 |
| abstract_inverted_index.been | 31 |
| abstract_inverted_index.long | 30 |
| abstract_inverted_index.most | 16 |
| abstract_inverted_index.real | 88 |
| abstract_inverted_index.rely | 19 |
| abstract_inverted_index.such | 9 |
| abstract_inverted_index.than | 64, 119 |
| abstract_inverted_index.that | 103 |
| abstract_inverted_index.this | 42, 74 |
| abstract_inverted_index.what | 120 |
| abstract_inverted_index.work | 40 |
| abstract_inverted_index.(LN), | 14 |
| abstract_inverted_index.BMSSP | 78, 107 |
| abstract_inverted_index.These | 131 |
| abstract_inverted_index.While | 26 |
| abstract_inverted_index.based | 94 |
| abstract_inverted_index.data. | 91 |
| abstract_inverted_index.first | 135 |
| abstract_inverted_index.shows | 102 |
| abstract_inverted_index.using | 87 |
| abstract_inverted_index.view. | 43 |
| abstract_inverted_index.where | 15 |
| abstract_inverted_index.which | 60 |
| abstract_inverted_index.(PCNs) | 8 |
| abstract_inverted_index.factor | 129 |
| abstract_inverted_index.faster | 63 |
| abstract_inverted_index.future | 147 |
| abstract_inverted_index.inform | 146 |
| abstract_inverted_index.paper, | 75 |
| abstract_inverted_index.recent | 38 |
| abstract_inverted_index.sparse | 36, 70 |
| abstract_inverted_index.tests, | 101 |
| abstract_inverted_index.theory | 121 |
| abstract_inverted_index.trials | 98 |
| abstract_inverted_index.(BMSSP) | 50 |
| abstract_inverted_index.BMSSP's | 139 |
| abstract_inverted_index.Bounded | 46 |
| abstract_inverted_index.Network | 13 |
| abstract_inverted_index.against | 85 |
| abstract_inverted_index.channel | 6 |
| abstract_inverted_index.clients | 17 |
| abstract_inverted_index.compare | 82 |
| abstract_inverted_index.current | 104 |
| abstract_inverted_index.graphs, | 37 |
| abstract_inverted_index.graphs. | 72 |
| abstract_inverted_index.optimal | 34 |
| abstract_inverted_index.payment | 5, 24 |
| abstract_inverted_index.provide | 133 |
| abstract_inverted_index.results | 132 |
| abstract_inverted_index.routing | 1, 144 |
| abstract_inverted_index.smaller | 118 |
| abstract_inverted_index.Shortest | 48 |
| abstract_inverted_index.achieves | 57 |
| abstract_inverted_index.constant | 128 |
| abstract_inverted_index.critical | 3 |
| abstract_inverted_index.directed | 71 |
| abstract_inverted_index.evidence | 137 |
| abstract_inverted_index.multiple | 96 |
| abstract_inverted_index.networks | 7 |
| abstract_inverted_index.possibly | 123 |
| abstract_inverted_index.regarded | 32 |
| abstract_inverted_index.runtime, | 59 |
| abstract_inverted_index.speedups | 116 |
| abstract_inverted_index.topology | 90 |
| abstract_inverted_index.Efficient | 0 |
| abstract_inverted_index.Lightning | 12 |
| abstract_inverted_index.algorithm | 28, 51 |
| abstract_inverted_index.currently | 18 |
| abstract_inverted_index.empirical | 136 |
| abstract_inverted_index.implement | 77 |
| abstract_inverted_index.n~log~n)$ | 68 |
| abstract_inverted_index.potential | 140 |
| abstract_inverted_index.practice, | 114 |
| abstract_inverted_index.predicts, | 122 |
| abstract_inverted_index.Dijkstra's | 27, 65, 86, 112 |
| abstract_inverted_index.accelerate | 142 |
| abstract_inverted_index.algorithms | 22 |
| abstract_inverted_index.challenges | 41 |
| abstract_inverted_index.outperform | 111 |
| abstract_inverted_index.overheads. | 130 |
| abstract_inverted_index.randomized | 97 |
| abstract_inverted_index.algorithms. | 152 |
| abstract_inverted_index.evaluation, | 93 |
| abstract_inverted_index.pathfinding | 151 |
| abstract_inverted_index.performance | 84 |
| abstract_inverted_index.statistical | 100 |
| abstract_inverted_index.theoretical | 39 |
| abstract_inverted_index.Multi-Source | 47 |
| abstract_inverted_index.pathfinding. | 25 |
| abstract_inverted_index.optimizations | 148 |
| abstract_inverted_index.significantly | 110 |
| abstract_inverted_index.theoretically | 56 |
| abstract_inverted_index.Dijkstra-based | 21 |
| abstract_inverted_index.asymptotically | 62 |
| abstract_inverted_index.implementation | 126 |
| abstract_inverted_index.implementations | 105 |
| abstract_inverted_index.$O(m~log^{2/3}~n)$ | 58 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |