負の重みの辺を含むグラフでも単一始点最短経路を正しく計算できるアルゴリズムはどれか？ 2026.01.31 負の重みの辺を含むグラフでも単一始点最短経路を正しく計算できるアルゴリズムはどれか？ ダイクストラ法 ベルマン–フォード法 幅優先探索（BFS） A*（エースター） ベルマン–フォード法は負の重みを持つ辺が存在する場合でも単一始点最短経路を計算でき、負のサイクルが存在するかどうかも検出できます。ダイクストラ法は負の辺があると誤った結果を出す可能性があり、BFSは重みが等しい（無重み）グラフ用、A*はヒューリスティックに依存する探索であり一般に負辺を扱う保証はありません。 クイズタグ: アルゴン関連記事 アルゴンクイズ！【問題 全10問・答え付き】 | 2026年01月版
