最短路の部分、mex 化

センサーネットワークのプログラムの一部にあった最短路だが、ボトルネックになっていたのでやはり mex にした。
もともと、スタート地点が一つでないため、Floyd–Warshall algorithm をベースにしていたが、アルゴリズムを整理したうえで mex にしたおかげで 30 倍程度の高速化になっている。
これによってボトルネックにならずに済みそうである。

ところで、最短路問題は基本的な問題であるため、非常に多くの実装があるし、ヒープなどを利用して高速化などが行なわれている。
しかし、スタート地点が複数でしかも全部の地点がスタートではない、という状況になるとあまり研究がなされていないようである。こういったときに、どれだけヒープなどで高速化できるのか、ということも良く解からないのか簡単には見つけることが難しい。

今日の作業内容：最短路 mex 化
明日の予測作業時間:5h