# Resource Constrained Pathfinding with A* and Negative Weights

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 83 references that are in the map.
- First posted on arXiv 14 Mar 2025.

## Builds on (most cited first, 14 of 14)

- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping](https://mlsanity.com/paper/1502.01063/) (2015)
- [An Equivalence Class for Orthogonal Vectors](https://mlsanity.com/paper/1811.12017/) (2018)
- [Enhanced Multi-Objective A* Using Balanced Binary Search Trees](https://mlsanity.com/paper/2202.08992/) (2022)
- [Dynamic Dynamic Time Warping](https://mlsanity.com/paper/2310.18128/) (2023)
- [If the Current Clique Algorithms are Optimal, so is Valiant's Parser](https://mlsanity.com/paper/1504.01431/) (2015)
- [More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture](https://mlsanity.com/paper/1805.08554/) (2018)
- [SETH Says: Weak Fr'echet Distance is Faster, but only if it is Continuous and in One Dimension](https://mlsanity.com/paper/1807.08699/) (2018)
- [Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles](https://mlsanity.com/paper/1904.03741/) (2019)
- [Induced Cycles and Paths Are Harder Than You Think](https://mlsanity.com/paper/2209.01873/) (2022)
- [Distributed Maximal Matching and Maximal Independent Set on Hypergraphs](https://mlsanity.com/paper/2211.01945/) (2022)
- [The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties](https://mlsanity.com/paper/2312.14593/) (2023)
- [Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs](https://mlsanity.com/paper/2409.08037/) (2024)

## Abstract (arXiv)

Constrained pathfinding is a well-studied, yet challenging network optimisation problem that can be seen in a broad range of real-world applications. Pathfinding with multiple resource limits, which is known as the Resource Constrained Shortest Path Problem (RCSP), aims to plan a cost-optimum path subject to limited usage of resources. Given the recent advances in constrained and multi-criteria search with A*, this paper introduces a new resource constrained search framework on the basis of A* to tackle RCSP in large networks, even in the presence of negative cost and negative resources. We empirically evaluate our new algorithm on a set of large instances and show up to two orders of magnitude faster performance compared to state-of-the-art RCSP algorithms in the literature.