On Computing Top-$k$ Simple Shortest Paths from a Single Source

• URL: http://arxiv.org/abs/2509.26094v1
• Date: Tue, 30 Sep 2025 11:12:05 GMT
• Title: On Computing Top-$k$ Simple Shortest Paths from a Single Source
• Authors: Mattia D'Emidio, Gabriele Di Stefano,
• Abstract summary: We investigate the problem of computing the top-$k$ simple shortest paths in weighted digraphs.<n>We show that our algorithm consistently and significantly outperforms the latter baseline in terms of running time.<n>These results establish our new algorithm as the solution to be preferred for computing $k$ simple shortest paths from a single source.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We investigate the problem of computing the top-$k$ simple shortest paths in weighted digraphs. While the single-pair variant -- finding the top-$k$ simple shortest paths between two specified vertices -- has been extensively studied over the past decades, with Yen's algorithm and its heuristic improvements emerging as the most effective solving strategies, relatively little attention has been devoted to the more general single-source version, where the goal is determining top-$k$ simple shortest paths from a source vertex to all other vertices. Motivated by the numerous practical applications of ranked shortest paths, in this paper we provide new insights and algorithmic contributions to this problem. In particular, we first present a theoretical characterization of the structural properties of its solutions. Then, we introduce the first polynomial-time algorithm specifically designed to handle it. On the one hand, we prove our new algorithm is on par, in terms of time complexity, with the best (and only) polynomial-time approach known in the literature to solve the problem, that is applying the fastest single-pair algorithm independently to each vertex pair formed by the source and the remaining vertices. On the other hand, through an extensive experimental evaluation on both real-world and synthetic graphs, we demonstrate that our algorithm consistently and significantly outperforms the latter baseline in terms of running time, achieving speed-ups of up to several orders of magnitude. These results establish our new algorithm as the solution to be preferred for computing $k$ simple shortest paths from a single source in practical settings.

Related papers

• Understanding Main Path Analysis [0.0]
  We show that entropy-based variants of main path analysis optimise geometric distance measures.<n>An approach based on longest paths produces similar results, is equally well motivated yet is much simpler to implement.<n>We introduce an approach using baskets'' of nodes where we select a fraction of nodes with the smallest values of a measure we call generalised criticality''
  arXiv  Detail & Related papers  (2025-12-13T14:59:21Z)
• Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization [3.3508820106803796]
  We analyze generalizations of algorithms based on the short-path framework first proposed by Hastings. Under some commonly satisfied technical conditions, an appropriate generalization can achieve super-quadratic speedups. We conclude the paper with a numerical analysis that guides the choice of parameters for short path algorithms.
  arXiv  Detail & Related papers  (2024-10-30T17:52:56Z)
• Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
  We introduce a novel approach based on the greedy algorithm by opt_einsum that computes efficient contraction paths in less time. With our approach, we are even able to compute paths for large problems where modern algorithms fail.
  arXiv  Detail & Related papers  (2024-05-08T09:25:39Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates [13.046825574678579]
  The shortest path problem in graphs is a cornerstone of AI theory and applications. We present a framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.
  arXiv  Detail & Related papers  (2022-08-22T22:07:27Z)
• A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs [19.873384058276713]
  A*Net is a scalable path-based method for knowledge graph reasoning. Inspired by the A* algorithm for shortest iteration path problems, our A*Net learns a priority function to select important nodes and edges at each.
  arXiv  Detail & Related papers  (2022-06-07T01:01:36Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
  Path finding is a well-studied problem in AI, which is often framed as graph search. We present two algorithms, grounded in the same idea, that can obtain provably optimal solutions to the considered problem.
  arXiv  Detail & Related papers  (2021-04-14T07:59:53Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  We propose a new low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from Leiden-k-cut. This proposed algorithm is scalable, outperforms state-of-the-art algorithms, and outperforms in real-world time with little additional cost.
  arXiv  Detail & Related papers  (2020-12-04T15:46:30Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.