【テキストデータ】応用情報技術者試験 令和6年度(2024年度) 春 午後 問３

「応用情報技術者試験 令和6年度(2024年度) 春 午後 問３」のテキストデータです。
テキストデータには「問題文(設問文含む)」「IPAからの解答例」「AIによる簡単な解説」が含まれます。
生成AIのプロンプトに入れて解説させる、などにご活用ください。

問3 グラフのノード間の最短経路を求めるアルゴリズムに関する次の記述を読んで、設問に答えよ。

グラフ内の二つのノード間の最短経路を求めるアルゴリズムにダイクストラ法がある。このアルゴリズムは、車載ナビゲーションシステムなどに採用されている。

【経路算定のモデル化】

グラフは、有界個のノードの集合と、その中の二つのノードを結ぶエッジの集合とから成る数理モデルである。ダイクストラ法による最短経路の探索問題を考えるに当たり、本問では、エッジをどちらの方向にも行き来することができ、任意の二つのノード間に経路が存在するグラフを扱う。ここで、グラフを次のように定義する。