令和6年度春期 応用情報技術者試験(AP)の午後問題3は、
に関する問題でした。
最短距離の算出プログラム(r06h_ap_pm3_1.py)
まずは、問題文中の図2で紹介されている最短距離の算出プログラムを作ってみました。
実行結果
% python r06h_ap_pm3_1.py 17
最短経路も出力するプログラム(r06h_ap_pm3_2.py)
最短距離の算出プログラムに最短経路も出力する機能を付け加えたものです。(図3,図4)
実行結果
% python r06h_ap_pm3_2.py 4 2 1 0 17
優先度付きキューを用いて性能を改善したプログラム(r06h_ap_pm3_3.py)
ノードの個数が少ないと効率の悪さを実感することはありませんが、問題文で紹介されているアルゴリズムは、更新起点ノードを求める処理の効率がよくありません。そこで、優先度付きキューを用いて書き換えてみました。
実行結果
% python r06h_ap_pm3_3.py 4 2 1 0 17
