# DataSP: A Differential All-to-All Shortest Path Algorithm for Learning Costs and Predicting Paths with Context

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 8 May 2024.

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

- [Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimization](https://mlsanity.com/paper/1603.00448/) (2016)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Differentiating Through a Cone Program](https://mlsanity.com/paper/1904.09043/) (2019)
- [Differentiable Dynamic Programming for Structured Prediction and Attention](https://mlsanity.com/paper/1802.03676/) (2018)
- [A Regularized Framework for Sparse and Structured Neural Attention](https://mlsanity.com/paper/1705.07704/) (2017)
- [PyEPO: A PyTorch-based End-to-End Predict-then-Optimize Library for Linear and Integer Programming](https://mlsanity.com/paper/2206.14234/) (2022)
- [Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach](https://mlsanity.com/paper/2106.03188/) (2021)
- [Survey on Vision-based Path Prediction](https://mlsanity.com/paper/1811.00233/) (2018)

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

- [Differentiable Generalized Sliced Wasserstein Plans](https://mlsanity.com/paper/2505.22049/) (2025)
- [Learning Solutions of Stochastic Optimization Problems with Bayesian Neural Networks](https://mlsanity.com/paper/2406.03082/) (2024)
- [Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity](https://mlsanity.com/paper/2505.21073/) (2025)
- [Inverse Optimization Latent Variable Models for Learning Costs Applied to Route Problems](https://mlsanity.com/paper/2509.15999/) (2025)
- [AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT](https://mlsanity.com/paper/2604.20744/) (2026)
- [When Evidence Changes the Subject: Subject-Typed Claim Licensing for Learned Routing](https://mlsanity.com/paper/2609.33505/) (2026)

## Abstract (arXiv)

Learning latent costs of transitions on graphs from trajectories demonstrations under various contextual features is challenging but useful for path planning. Yet, existing methods either oversimplify cost assumptions or scale poorly with the number of observed trajectories. This paper introduces DataSP, a differentiable all-to-all shortest path algorithm to facilitate learning latent costs from trajectories. It allows to learn from a large number of trajectories in each learning step without additional computation. Complex latent cost functions from contextual features can be represented in the algorithm through a neural network approximation. We further propose a method to sample paths from DataSP in order to reconstruct/mimic observed paths' distributions. We prove that the inferred distribution follows the maximum entropy principle. We show that DataSP outperforms state-of-the-art differentiable combinatorial solver and classical machine learning approaches in predicting paths on graphs.