北京地下鉄駅線路計画

774 ワード

プロジェクトの内容
北京地下鉄路線の計画プログラムを設計する
開発言語
  java
需要分析
1.ユーザーは線路計画状況を見ることができ、自分で線路を選択することができる
2.ユーザーは始点と終点を入力してサイトの最低と乗り換えの最低のルートを調べることができる
実装方法
1.サイト情報を2 D配列に格納する
2.Dijkstraアルゴリズムを用いて最短経路を得る
3.得られた最短パスを1枚のテーブルに格納する
4.テーブルに格納されている最短パス情報をユーザーにフィードバックする
5.再帰アルゴリズムで最低乗り換え路線を得る
6.最低乗り換え路線が通過する駅の総数を計算し、小さい総数で大きい総数をカバーし、ユーザーにフィードバックする
 
試験例
入力
  :  1
  :  2

しゅつりょく
    :
  1->  1->......->  2
    :
  1->  1->......->  2

 
実験のまとめ
サイト数が多くない場合は,最適解を事前に保存しておき,ユーザはデータを取得する際に繰り返し計算ではなく直接データを読み取ることができる.