平成24年度秋季 基本情報技術者試験(FE)の午後問題8は、
- Warshall-Floyd法(ワーシャルフロイド法)を用いて鉄道駅間の最短距離を求める
問題でした。
鉄道の路線から最短距離を求めるという身近な題材であり、これが発展したものがYahoo!などが提供している「乗換案内」アプリにつながっているのかもしれないと思うと、中々楽しい題材だなと思います。
問題を解くだけではもったいないので、問題文中に示されている図3、図4に値を追加(赤字赤い文字)してシミュレーションしてみました。
プログラム例(h24a_fe_pm8.c)
実行結果
駅1から駅3への最短距離
駅2を経由していく路線が最短のようです。
区間を指定 => 1 3 最短距離 = 35
駅6から駅4への最短距離
「駅6 → 駅3 → 駅2 → 駅10 → 駅4」と辿るのが最短のようです。
区間を指定 => 6 4 最短距離 = 50
駅5から駅4への最短距離
「駅5 → 駅1 → 駅2 → 駅10 → 駅4」と辿るのが最短のようです。 駅6へ向かったら遠回りになるようですね。
区間を指定 => 5 4 最短距離 = 50
