# Incremental Approximate Single-Source Shortest Paths with Predictions

arXiv: https://arxiv.org/abs/2502.08125 · HTML: https://mlsanity.com/paper/2502.08125/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 47 references that are in the map.
- First posted on arXiv 12 Feb 2025.

## Builds on (most cited first, 30 of 31)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Online Algorithms for Weighted Paging with Predictions](https://mlsanity.com/paper/2006.09509/) (2020)
- [Predictive Flows for Faster Ford-Fulkerson](https://mlsanity.com/paper/2303.00837/) (2023)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Learning-Augmented Maximum Flow](https://mlsanity.com/paper/2207.12911/) (2022)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [On Dynamic Graph Algorithms with Predictions](https://mlsanity.com/paper/2307.09961/) (2023)
- [On the Complexity of Algorithms with Predictions for Dynamic Graph Problems](https://mlsanity.com/paper/2307.16771/) (2023)
- [Online Page Migration with ML Advice](https://mlsanity.com/paper/2006.05028/) (2020)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Robust Learning-Augmented Dictionaries](https://mlsanity.com/paper/2402.09687/) (2024)
- [Online List Labeling with Predictions](https://mlsanity.com/paper/2305.10536/) (2023)
- [The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations](https://mlsanity.com/paper/2307.08890/) (2023)
- [Incremental Topological Ordering and Cycle Detection with Predictions](https://mlsanity.com/paper/2402.11028/) (2024)
- [Competitive strategies to use "warm start" algorithms with predictions](https://mlsanity.com/paper/2405.03661/) (2024)
- [Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler](https://mlsanity.com/paper/2001.10809/) (2020)
- [Daisy Bloom Filters](https://mlsanity.com/paper/2205.14894/) (2022)
- [Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs](https://mlsanity.com/paper/1504.07959/) (2015)
- [Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs](https://mlsanity.com/paper/1612.03856/) (2016)
- [Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2101.07149/) (2021)
- [Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier](https://mlsanity.com/paper/2110.11712/) (2021)
- [Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization](https://mlsanity.com/paper/1308.0776/) (2013)
- [New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs](https://mlsanity.com/paper/2001.10751/) (2020)
- [Near-Optimal Decremental SSSP in Dense Weighted Digraphs](https://mlsanity.com/paper/2004.04496/) (2020)

## Built on by (most cited first, 3 of 3)

- [Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion](https://mlsanity.com/paper/2602.24232/) (2026)
- [Incremental Strongly Connected Components with Predictions](https://mlsanity.com/paper/2604.26062/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

The algorithms-with-predictions framework has been used extensively to develop online algorithms with improved beyond-worst-case competitive ratios. Recently, there is growing interest in leveraging predictions for designing data structures with improved beyond-worst-case running times. In this paper, we study the fundamental data structure problem of maintaining approximate shortest paths in incremental graphs in the algorithms-with-predictions model. Given a sequence σ of edges that are inserted one at a time, the goal is to maintain approximate shortest paths from the source to each vertex in the graph at each time step. Before any edges arrive, the data structure is given a prediction of the online edge sequence hatσ which is used to ``warm start'' its state. As our main result, we design a learned algorithm that maintains (1+ε)-approximate single-source shortest paths, which runs in tildeO(m η log W/ε) time, where W is the weight of the heaviest edge and η is the prediction error. We show these techniques immediately extend to the all-pairs shortest-path setting as well. Our algorithms are consistent (performing nearly as fast as the offline algorithm) when predictions are nearly perfect, have a smooth degradation in performance with respect to the prediction error and, in the worst case, match the best offline algorithm up to logarithmic factors. As a building block, we study the offline incremental approximate single-source shortest-paths problem. In this problem, the edge sequence σ is known a priori and the goal is to efficiently return the length of the shortest paths in the intermediate graph Gt consisting of the first t edges, for all t. Note that the offline incremental problem is defined in the worst-case setting (without predictions) and is of independent interest.