# A fast algorithm for the gas station problem

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2017.

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

- [Heuristic Search for Path Finding with Refuelling](https://mlsanity.com/paper/2309.10796/) (2023)

## Abstract (arXiv)

In the gas station problem we want to find the cheapest path between two vertices of an n-vertex graph. Our car has a specific fuel capacity and at each vertex we can fill our car with gas, with the fuel cost depending on the vertex. Furthermore, we are allowed at most Delta stops for refuelling. In this short paper we provide an algorithm solving the problem in O(Delta n2 + n2logn) steps improving an earlier result by Khuller, Malekian and Mestre.