{"id":"arxiv:2602.16153","kind":"preprint","title":"Bellman-Ford in Almost-Linear Time for Dense Graphs","authors":["George Z. Li","Jason Li","Junkai Zhang"],"author_count":3,"year":2026,"published":"2026-02-18","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2602.16153","nct_id":null,"source_url":"https://arxiv.org/abs/2602.16153","archive_url":"https://space-kitty.com/papers/arxiv:2602.16153","updated":"2026-02-18","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2602.16153","abstract":"We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in $n^{2+o(1)}$ time by refining the shortcutting procedure introduced in Li, Li, Rao, and Zhang (2026).","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}