ヒープ付きダイクストラ法。

卒業研究のときに作成したプログラムものを、この前頂いたプログラムを参考に改善してみた。
異なる点は以下のとおりである。

　　　　　　　　　　　 自分　　　　　　　 　　頂いたプログラム
１、ヒープの実装方法　ポインタ　　　　or　　　配列
２、メモリ確保方法　　ノード単位　　　or　　　アーク単位
３、動的静的？　　　　動的確保　　　　or　　　静的確保
４、変数の定義　　　　グローバルなし　or　　　グローバル
５、実行方法　　　　　始点終点　　　　or　　　クエリファイル
６、グラフファイル　　Dimacsそのまま　or　　　修正Dimacs（ソート＆数字のみ）

今回、２のメモリの確保方法をアーク単位にすることでかなりのメモリ消費を抑えるとともに、５のクエリファイルを導入することでより実行しやすいように改善された。またメモリ消費もすくなったので、全体的に動作が軽くなったといえる。また６のように予めグラフファイルにソート等を施すことで、データ入力が大きく改善された。

例に「USA-road-d.FLA.gr」という、点数1,070,376 枝数2,712,798 のグラフデータから、以下のようなクエリファイルを用いて実行した。



5　　　　　　　// クエリ数
1 6 　　　　　// 1 から 6 まで
1 76　　　　　// 1 から 76 まで
1 376 　　　　// 1 から 376 まで
1 70376　　　// 1 から 70376 まで
1 1070376 　// 1 から 1070376 まで



　　　　　　　　　実行時間（ファイル入力は含めない）
頂いたプログラム 1000[ms]前後
作ったプログラム　500[ms]前後


前処理などは行っていないので、これからどのような展開になるか楽しみだ。