応用情報技術者 試験情報＆徹底解説

平成18年度 春期 ソフトウェア開発技術者試験 午後I 問5 設問3 (1) について
問題冊子:
 www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2006h18_1/2006h18h_sw_pm1_qs.pdf
解答例:
 www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2006h18_1/2006h18h_sw_pm1_ans.pdf

2013-3-14現在のIPAの解答例では、previousの挿入箇所は(ウ)であるとありますが、ただしくは(エ)では無いでしょうか？
問題文中の記述に似せて、以下の検証プログラムで確認してみました

gist.github.com/tono-nakae/4966113

結論から申しますと、挿入位置は(ウ)で、IPAの解答が正しいと思います。

IPAの解答例では、
  previous[i] <- nodeNumber
と、添字が[i]になっています。
挿入位置(ウ)は、他ルートからの距離の方が短い場合を発見した場合です。
この時の添字[i]を使わないと、どのノードを見ているか分かりません。

小野@岡山さんの検証プログラムの結果を見ると、
previous(ウ) => {1: None, 2: 3, 3: 2, 4: None, 5: None}
previous(エ) => {1: 1, 2: 3, 3: 2, 4: 4, 5: 5}
「各ノードに至る経路の最後のエッジがどのノードから来たか」を表していません。

小野@岡山さんの検証プログラムを良く見ると、
  previous_U[j] = nodeNumber
  previous_E[j] = nodeNumber
と、添字が[j]になっています。[j]が示すのは、始点ノードの番号です。
「他ルートからの距離の方が短い場合」を発見したときに、
始点ノードのprevious[j]を書き換えても意図しない結果になります。

これを[i]に直してpythonプログラムを動作させると、意味が分かると思います。

誤字脱字ありましたら申し訳ありません。

失礼しました、IPA回答例のプログラムへの落とし込みに誤りがありました。お詫びいたします。

ご指摘いただいた、(ウ)の挿入式を previous_U[i] = nodeNumber に修正してpythonプログラムを動作させてみましたところ、以下のように(ウ)での経路縮退操作が行われた時のみpreviousにノードが記録されました。（(ウ)での操作を便宜上「経路縮退操作」とよばせて頂いてます）

previous(ウ) => {1: None, 2: 3, 3: None, 4: 2, 5: 3}

しかし、問題文でのpreviousの定義では「最短距離で移動するときの経路を示すもの」とあります。
ここで「最短距離」については問題文中③の「その時点でのノードnの距離をnの最短距離として確定し...」とあることから、経路縮退操作を行わなかった場合の移動も「最短距離」であると読めます。
したがって、previousの結果には未定義状態(None)が存在することは許されないと考えるのですが、これは本来どのように解釈するのが正しいのでしょうか？

やっと出題者の意図がわかりました。

previousの定義「最短距離で移動するときの経路を示すためにprevious[N_NODE]を導入する」の文意は、「previous＝最短距離で移動するときの経路」では*なく*、「最短経路で移動する経路を求めるための必要情報としてpreviousを導入する」という事ですね。

(1)での「最短経路を記録するためには...」とあるのも同様に、「最短経路を求めるために必要な情報を収集するためには...」と読み手が行間を読まなければいけないという事ですか。

計２ヶ所のミスリーディングを誘う落とし穴を避ける、国語力が問われていたのですね。
仕様書でこんな書き方したらクビが飛ぶんですけどね