アルゴリズムとプログラミングアルゴリズムとデータ構造

5頂点のグラフでダイクストラ法を使い頂点Aから頂点Eへの最短路を求める。辺の重みは A-B=4, A-C=2, B-D=3, B-E=6, C-D=1, C-E=5, D-E=2 とする。A→Eの最短距離はどれか。

ア.4

イ.5正解

ウ.6

エ.7

解説

ダイクストラ法は「カーナビの最短ルート計算」。すべての交差点への最短距離を確定させながら進む。

なぜイが正解か

A→B: 4, A→C: 2。CからDへ: 2+1=3, CからEへ: 2+5=7。DからEへ: 3+2=5。BからEへ: 4+6=10。最短はA→C→D→E=2+1+2=5。答えは5。

なぜアは間違いか

4はA→Bの辺の重みであり、Eまでの最短距離ではない。

なぜウは間違いか

6はA→B→D→E=4+3+2=9やA→C→E=2+5=7より小さいが、5が正解なのでウは誤り。

なぜエは間違いか

7はA→C→E=2+5=7のルートだが、A→C→D→E=5のほうが短い。

出典: AI生成問題（学習用）

← 前の問題

サイズ7のハッシュテーブルでダブルハッシュ法を使用する。h1(k)=k mod 7、h2(k)=1+(k mod 5)。スロット1がすでに占有されている状態でキー36を挿入するとき、最終的に格納されるインデックスはどれか。

次の問題 →

4頂点グラフにプリム法で最小全域木を求める。辺の重みは A-B=2, A-C=4, A-D=7, B-C=1, B-D=5, C-D=3 とする。最小全域木の総コストはどれか。