Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study

Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota OtachiAAAI 2022 · DOI

Introduction

In traditional optimization, the goal is typically to find a single optimal solution, such as the shortest path between two points. However, real-world decision-making often involves "hidden" constraints—aesthetic preferences, political factors, or dynamic conditions like traffic—that are difficult to model mathematically. While standard "top-$k$ enumeration" algorithms can provide multiple solutions, these are often nearly identical, differing by only a few elements. This lack of variety limits their utility for users who need distinct alternatives.

This paper addresses the Diverse X Paradigm: given an integer $k$, the goal is to find $k$ feasible solutions that are not only optimal but also maximally diverse, as measured by the sum of their pairwise Hamming distances.

Methodology: The k-Packing Framework

The core contribution of this work is a general reduction technique that transforms the diversity-maximization problem into a weighted $k$-packing problem.

The k-Packing Trick

For every element in the original set (e.g., an edge in a graph), the algorithm creates $k$ copies. Each copy $i$ is assigned a weight $w^*(e_i) = w(e) \cdot (k - 2i + 1)$. This linear weighting scheme incentivizes the selection of distinct elements for each of the $k$ solutions, effectively linearizing the quadratic objective of maximizing pairwise distances. This allows the problem to be solved using standard, efficient tools like Minimum Cost Flow algorithms.

Application to Shortest Paths

To find diverse shortest $st$-paths, the authors extract the Directed Acyclic Graph (DAG) of all absolute shortest paths. They then apply the $k$-packing trick to the edges of this DAG. This approach also generalizes to other combinatorial structures, such as weighted matroid bases, arborescences, and bipartite matchings.

Experimental Evaluation

The authors evaluated the proposed algorithm across three distinct graph types:

  1. Synthetic Grid Graphs: $p \times p$ grids designed as a "stress test" where every edge belongs to at least one shortest path.
  2. SNAP Datasets: Real-world social networks (e.g., Wiki-Vote, Twitter) characterized by low diameters.
  3. DIMACS Road Networks: Large-scale road networks for New York (NY) and Florida (FL), containing millions of edges.

Key Results and Analysis

The experimental results demonstrate a significant improvement in solution variety with a manageable increase in computational cost.

Diversity Gains

As shown in the comparison below, the proposed framework consistently achieves significantly higher diversity measures compared to traditional $k$-best enumeration (e.g., Eppstein’s algorithm). This advantage is maintained across varying values of $k$ and grid dimensions, proving that the algorithm successfully finds distinct paths where standard methods fail.

Diversity measure comparison on synthetic grid graphs, showing the proposed method consistently outperforms k-best enumeration.

Computational Performance and Scalability

While maximizing diversity is more computationally intensive than simple enumeration, the algorithm remains highly scalable. On the Florida road network, which features 2.7 million edges, the algorithm generated 10 diverse paths in approximately 6 seconds. On synthetic grid graphs, the processing time scales predictably, as seen in the following figure.

Processing time comparison on synthetic grid graphs, illustrating the scaling behavior of the diversity-maximizing framework.

Theoretical Boundaries

A key theoretical finding is the sharp complexity boundary between absolute and "nearly" shortest paths. While finding diverse absolute shortest paths is solvable in polynomial time, the authors prove that finding diverse paths that are slightly longer than the minimum is NP-hard. This highlights the challenge of balancing optimality with diversity when the set of optimal solutions is small; in graphs with a unique shortest path, the algorithm would simply return the same path $k$ times.

Conclusion

This study provides a robust, polynomial-time framework for generating diverse optimal solutions to complex combinatorial problems. By reducing diversity to a flow problem, the authors offer a practical tool for large-scale applications like GPS routing. Future work may explore alternative diversity measures, such as maximizing the minimum distance between any two solutions, or optimizing performance for extremely dense graph instances.

Summary updated

BibTeX
@inproceedings{hanaka2022computing,
  author = {Tesshu Hanaka and Yasuaki Kobayashi and Kazuhiro Kurita and See Woo Lee and Yota Otachi},
  title = {{Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i4.20290},
}

Loading related content...

Figure