データ構造とアルゴリズム
ダイクストラ法で正しい最短経路が求められるための、グラフについての条件として正しいものはどれか。
- Aグラフに閉路(同じ頂点に戻ってくる経路)がないこと
- B辺に向きがないこと
- C辺の重みがすべて0以上であること
答えと解説を見る
正解：C. 辺の重みがすべて0以上であること
ダイクストラ法は、未確定の頂点のうち最も距離の小さいものを確定させます。これは、ほかの頂点を経由すると距離が増えることはあっても減ることはない、という前提に基づいています。負の重みの辺があると、後から別の経路で距離が短くなることがあり、例えば S→A が2、S→B が3、B→A が−2 の有向グラフでは、A を2で確定した後に S→B→A の1が見つかります。負の重みがあるときはベルマン・フォード法などを使います。閉路があっても、辺に向きがあっても、重みが0以上であればダイクストラ法は使えます。
- A. 閉路があっても、重みが0以上なら正しく求められます。道路網には閉路がたくさんあります。
- B. 向きのある(有向)グラフでも使えます。
- C. 正しい。負の重みがあると、確定した距離が後から短くなることがあります。