# Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 36 references that are in the map.
- First posted on arXiv 10 Dec 2021.

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

- [Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory](https://mlsanity.com/paper/1903.07410/) (2019)
- [JGraphT -- A Java library for graph data structures and algorithms](https://mlsanity.com/paper/1904.08355/) (2019)
- [FPT Algorithms for Diverse Collections of Hitting Sets](https://mlsanity.com/paper/1911.05032/) (2019)
- [Diverse Pairs of Matchings](https://mlsanity.com/paper/2009.04567/) (2020)
- [Finding Diverse Trees, Paths, and More](https://mlsanity.com/paper/2009.03687/) (2020)
- [Diverse Collections in Matroids and Graphs](https://mlsanity.com/paper/2101.04633/) (2021)
- [k-best enumeration](https://mlsanity.com/paper/1412.5075/) (2014)

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

- [PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization](https://mlsanity.com/paper/2402.14048/) (2024)
- [Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem](https://mlsanity.com/paper/2404.11496/) (2024)

## Abstract (arXiv)

Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study the following type of problems: given an integer k, the problem asks for k solutions such that the sum of pairwise (weighted) Hamming distances between these solutions is maximized. Such solutions are called diverse solutions. We present a polynomial-time algorithm for finding diverse shortest st-paths in weighted directed graphs. Moreover, we study the diverse version of other classical combinatorial problems such as diverse weighted matroid bases, diverse weighted arborescences, and diverse bipartite matchings. We show that these problems can be solved in polynomial time as well. To evaluate the practical performance of our algorithm for finding diverse shortest st-paths, we conduct a computational experiment with synthetic and real-world instances.The experiment shows that our algorithm successfully computes diverse solutions within reasonable computational time.