DijkstraとFloyd-Warshallの最短経路アルゴリズムの実装をtoysolverに放り込んだ[1]。 きっかけは Google Code Jam 2017 Round 1B の Problem C. Pony Express [2]。

Dijkstraは何度も実装してるけど、Haskellで実装するときは毎回プライオリティキュー実装のライブラリをどれを使うかとか、そのライブラリの使い方を調べるのとかで、時間を取られているので。 今回のはtoysolverではもともとグレブナー基底の計算とかでも使っていたheaps[3]を使った。

Floyd-Warshallは、Pony Express に関してはDijkstraだけで解けてしまうのだけれど、後半はFloyd-Warshallを使うのが自然だし、これまで書いたことなかったので、一度書いておきたいなと思って。

[1] https://github.com/msakai/toysolver/commit/b72c6a8f6cdcfd937fdf5e96ef223104ec9ad035

[2] Problem C. Pony Express
https://code.google.com/codejam/contest/8294486/dashboard#s=p2

[3] heaps
http://hackage.haskell.org/package/heaps