私が使用boost::graphしているのは、その Dijkstra 実装です。
一連の頂点から別の一連の頂点までの最短経路を計算したいと考えています。これらのセット間のすべての可能なパスを計算したくありません。
アイデアは次のとおりです。さまざまな通りに入り口がある建物にいます。そのため、どの通りからでも旅を始めることができます。しかし、私は最短のものにしか興味がありません。
ダイクストラのアルゴリズムの独自の実装を使用した場合、次のようにします。
- 開始ノードごとに、距離は 0 にマップされます
- 開始ノードを優先キューに追加します。
を使用して距離マップを 0 に設定するのは簡単boost::dijkstra_shortest_paths_no_initですが、ノードをプライオリティ キューに追加する方法がわかりません。ソースコードを調べたところ、ほとんど不可能のようです。そこで、開始ノードの 1 つに到達した場合に 0 の距離を返す独自の結合ファンクターを定義することを考えていますが、かなり醜いようです。
仮想ノードを作成し、仮想ノードから開始ノードにエッジを追加できます。ただし、これにより、回避したい同時アクセスの問題がいくつか発生します。
ブーストライブラリの可能性を見逃したのですか、それとも誰かが巧妙な回避策を知っていますか? また、プライオリティ キューのカスタム初期化を可能にするために、boost にパッチを適用することも考えています。