単一始点最短経路を求めるアルゴリズム Bellman–Ford が追加で検出できるものは次のうちどれか? 2026.01.31 単一始点最短経路を求めるアルゴリズム Bellman–Ford が追加で検出できるものは次のうちどれか? 負の重みを含むサイクル(負のサイクル)の存在 全ての負辺を正に変換する変換方法 最短路の個数が無限であること 任意の重み付きグラフが非負重みであること Bellman–Ford 法は反復的に緩和操作を行い、最大で頂点数-1 回の反復で最短距離を求めます。さらに追加の反復を行うことで、距離がさらに更新される(さらに短くなる)経路があれば負の重みサイクルが存在すると判定できます。したがって負のサイクルの検出が可能であり、これは Dijkstra 法では直接行えない特性です。 クイズタグ: アルゴン関連記事 アルゴンクイズ!【問題 全10問・答え付き】 | 2026年01月版