論文の概要: On Computing Top-$k$ Simple Shortest Paths from a Single Source
- arxiv url: http://arxiv.org/abs/2509.26094v1
- Date: Tue, 30 Sep 2025 11:12:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-01 17:09:04.516177
- Title: On Computing Top-$k$ Simple Shortest Paths from a Single Source
- Title（参考訳）: 単一ソースからの単純なショートパスのトップ$kコンピューティングについて
- Authors: Mattia D'Emidio, Gabriele Di Stefano,
- Abstract要約: 重み付きダイグラフにおける最上位$kの単純な最短経路の計算問題について検討する。
我々は,本アルゴリズムが実行時間において,後者のベースラインよりも連続的に,著しく優れていることを示す。
これらの結果は,1つのソースからの単純な最短経路を$k$で計算するソリューションとして,我々の新しいアルゴリズムを確立している。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 重み付きダイグラフにおける最上位$kの単純な最短経路の計算問題について検討する。
シングルペアの変種 -- 指定された2つの頂点間の最短パスのトップ$kを見いだす -- は、Yenのアルゴリズムとそのヒューリスティックな改善によって、過去数十年にわたって広く研究されてきたが、より一般的なシングルソースバージョンには比較的注意が向けられていない。
最短経路の多くの実践的応用に触発された本論文では,この問題に対する新たな洞察とアルゴリズム的貢献について述べる。
特に、まずその解の構造的性質の理論的特徴を示す。
次に,その処理に特化して設計された最初の多項式時間アルゴリズムを提案する。
一方,本アルゴリズムは時間的複雑性の観点からも同等であり,この問題を解くために文献で知られている最良(かつ唯一の)多項式時間アプローチであり,ソースと残りの頂点が生成する頂点対に対して,最も高速な単対アルゴリズムを適用している。
一方,実世界のグラフと合成グラフの双方に対する広範な実験的評価により,本アルゴリズムは実行時間の観点から連続的に,かつ有意に性能が向上し,最大数桁のスピードアップが達成されることを示した。
これらの結果から,実運用環境での単一ソースからの単純な最短経路を$k$で計算する手法として,我々の新しいアルゴリズムを確立した。
関連論文リスト
- Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization [3.3508820106803796]
本稿ではHastingsが最初に提案したショートパスフレームワークに基づいてアルゴリズムの一般化を分析する。
一般的に満たされているいくつかの技術的条件の下では、適切な一般化は超4次スピードアップを達成することができる。
本論文は,短経路アルゴリズムのパラメータ選択を導く数値解析で締めくくった。
論文 参考訳（メタデータ） (2024-10-30T17:52:56Z) - Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
より少ない時間で効率的な収縮経路を計算できる opt_einsum による欲求アルゴリズムに基づく新しい手法を提案する。
我々のアプローチでは、現代のアルゴリズムが失敗する大きな問題に対するパスを計算できる。
論文 参考訳（メタデータ） (2024-05-08T09:25:39Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - A Generalization of the Shortest Path Problem to Graphs with Multiple
Edge-Cost Estimates [13.046825574678579]
グラフにおける最短経路問題は、AI理論と応用の基礎である。
本稿では,エッジウェイトを複数回(推定)計算できる重み付き有向グラフのフレームワークを提案する。
次に、一般化問題に対する2つの完全アルゴリズムを提示し、その有効性を実証的に示す。
論文 参考訳（メタデータ） (2022-08-22T22:07:27Z) - A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs [19.873384058276713]
A*Netは知識グラフ推論のためのスケーラブルなパスベースの手法である。
最短繰り返しパス問題に対するA*アルゴリズムにインスパイアされた我々のA*Netは、それぞれに重要なノードとエッジを選択する優先度関数を学習する。
論文 参考訳（メタデータ） (2022-06-07T01:01:36Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
パス探索は、しばしばグラフ検索としてフレーム化されるAIのよく研究された問題です。
同じアイデアを基礎とした2つのアルゴリズムを提示し,検討した問題の最適解を求める。
論文 参考訳（メタデータ） (2021-04-14T07:59:53Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。