[c++]Boostのdijkstra_shortest_paths()

Cで、dijkstra法による経路探索を行いたかった。
最短の経路探索法なら何でもよいのだが、思いつくのがdijkstra先生の方法しかなかったのだ。

一応、大昔に受けた授業でやった記憶だけは残っている。
動的計画法だのなんだのかんだの。
だから、アルゴリズムの本を読めば記憶が甦ってくるんじゃなかろうかと期待したのだが、うん、ダメだね。

そして最初に書いたように、経路探索を行いたいだけで、別に経路探索するアルゴリズムを自分で実装したいわけではない。
ライブラリでもサンプルソースでも、動けばよかろうなのだ。

よかろうなのだが、なかなか気に入ったソースが見つからない。
よく見るのは、M x Nの2次元配列を作るタイプだ。
しかし、今回は動的に増えていくので、そういう書き方だとやりづらいし、メモリをいっぱい使うことになるので嫌だ。

1ヶ所見つけたのだが、そこはサイトがGPL1.2で、これはこれでよろしくない。
もう少しゆるめのライセンスがよいのだ。

そこで妥協したのが、C++にすることだった。
今作っているCのライブラリさえ使えればよいので、C++でもよいのだ。

C++といえば、やはりBoostよね。

---

Boost Graph Library: Dijkstra's Shortest Paths - 1.65.0

うーん。。。すごく見づらいぞ。
蛇のアイコンもあるし、pythonと関係あるのか？

もっとわかりやすいサイトがあるはず、と探すと、ありました。
グラフ - boostjp
ありがたいことに日本語だ。

始点Sから終点Zまでの経路探索をするサンプルになっている。
ノード・・・じゃなくてvertexと表現している。頂点か。
そして、頂点と頂点を結ぶ辺をedgeという。
edgeには重みがあり、それはweightだ。

というのはサンプルソースの最初の方を読んでなんとなく分かったが、型とか使い方になるとサンプルソースを読んでも今ひとつ分からない。
いきなりdijkstraのところからやるのではなく、Boostのgraphというものについての考え方や方針を把握した方がよさそうだ。
これも同じページの最初の方に書かれている。

が、しかしこれは・・・複雑だ。
日本語で説明してあって、さらに例まで載っているからわかるものの、そうじゃなかったら使い切れない気がする。