令和3年度 III-4

解説

この問題で問われていること

Dijkstra法を実際に手順どおり実行し、最短距離が確定する順序を求める問題。

解き方

① Dijkstra法: 未確定のノードのうち距離が最小のものを確定し、そこから隣の距離を更新する
② S(0)→B(5)確定: A=8、C=14、D=7に更新 → D(7)確定: C=13 → A(8)確定: C=9 → C(9)確定
③ S B D A C(④)

正解が正しい理由

Dijkstra法は、未確定ノードのうち始点からの暫定距離が最小のものを順に確定し、その隣接ノードの暫定距離を更新する。初期状態でSは0。S→A=10、S→B=5なので、最小のBが確定(5)。Bから、A=5+3=8(更新)、C=5+9=14、D=5+2=7。次に最小のD(7)が確定。DからC=7+6=13に更新。次にA(8)が確定し、AからC=8+1=9に更新。最後にC(9)が確定する。確定順はS、B、D、A、Cとなり、④が正しい。

各選択肢について

• ① S、A、B、C、Dの順は、Sに隣接するノードのうち距離10のAを先に確定しており、距離5のBが先になるため誤り。
• ② S、A、C、B、Dも、最初にAを選んでおり誤り。
• ③ S、B、A、D、Cは、Bの次にA(8)を選んでいるが、D(7)の方が小さいので、Dが先。
• ④ S、B、D、A、Cは、確定順(距離 0、5、7、8、9)と一致する。これが正答。
• ⑤ S、B、C、A、Dは、Cの暫定距離が14と大きい段階でCを選んでいて、誤り。

覚えるべきポイント

Dijkstra法は、暫定距離が最小の未確定ノードを1つずつ確定し、隣接ノードの距離を緩和(更新)する。確定順は、始点からの最短距離の昇順になる。