2017/09/01

[c++]Boostのdijkstra_shortest_paths() - 2

意外なことに、2回目です。
前回はこちら


グラフ - boostjp
このサイトを見て、探索はできるようになったのだが、あまりにも理解できなさすぎて、応用がまったくできない。
理論はもうあきらめるとして(いいのか。。。)、主な使い方くらいは覚えよう。


ツリーではなく、グラフだ。
だから、ノードやブランチではなく、vertexやedgeと呼ぶようだ。
まあ、ツリーでもedgeを使ったりするようなので、そこまで依存した言葉遣いではないのだろう。


このグラフ全体をclass adjacency_listが持つようだ。
派生して使うのではなく、templateになっていて、テンプレートパラメータを指定することでグラフ全体の設定になるようだ。

説明はサイトを読んだ方が早いだろう。
主に変更しそうなものは、グラフの有向(一方向、双方向)/無向と、カスタムプロパティかな。
双方向有向が無向と違うのは、重みが方向によって替えられたり、辺によって一方向にすることができる、というところか。
細かいけど、片方向はdirectedS、無向はundirectedSだけど、双方向はbidirectionalSと末尾が違うので注意だ。


こんな感じで、じわじわ読み進めていこう。

主な使い方、と最初に書いたものの、それですらいつ終わるかわからんが、やらねば終わらぬのだ。

0 件のコメント:

コメントを投稿

コメントありがとうございます。
スパムかもしれない、と私が思ったら、
申し訳ないですが勝手に削除することもあります。