平成26年度秋期 応用情報技術者試験 午前 問5

正解：イ

AI解説

始点V1から各頂点への最短所要時間は、ダイクストラ法の要領で「確定した頂点から伸びる辺で各頂点への合計時間を更新し、最小のものから確定する」ことで求める。直行する経路よりも他の頂点を経由する経路の方が短い場合がある点に注意して全経路を比較すると、最短所要時間はV4が最も短く、次いでV6、最も長いのがV5となり、V4、V6、V5の順である。 ア: V4、V5、V6の順は、V5とV6の最短時間の大小を誤っている。V5へは見かけの直行経路より他経由が絡み、V6より時間がかかる。 イ: 正解。最短所要時間を短い順に並べるとV4、V6、V5となる。 ウ: V5を最短としているが、V4への最短時間の方が短いため誤りである。 エ: 同じくV5を先頭にしており、V4より短いとしている点で誤りである。 💡 最短経路問題は「直接つながる辺の値」だけで判断せず、経由路を含めて頂点ごとに最小値を確定していくこと。試験では表を書いて距離を更新すると確実である。