ダイクストラ法（Dijkstra）が単一始点最短経路問題に対して正しく適用できるための必要十分の条件はどれか？ 2026.01.31 ダイクストラ法（Dijkstra）が単一始点最短経路問題に対して正しく適用できるための必要十分の条件はどれか？ グラフが有向であること 全ての辺の重みが非負であること 始点から到達できる頂点数が有限であること グラフが連結であること ダイクストラ法は頂点の最短距離が確定した順に確定させる貪欲法で、エッジの重みが非負であることが計算の正当性の鍵です。負の辺があると、すでに確定した距離が後で小さくなる可能性があり誤った結果になります。グラフの有向・無向や連結性は状況により扱えますが、正しさの前提は「辺の重みが非負であること」です。 クイズタグ: アルゴン関連記事 アルゴンクイズ！【問題 全10問・答え付き】 | 2026年01月版
