私は自分のプロジェクトでLEMON ライブラリを使用していますが、特定のセット内の頂点間の完全な距離行列を評価するために LEMON ライブラリをどのように使用するのが最適か疑問があります。
ListDigraphしたがって、頂点のサブセットである大きなグラフ ( として表される) が与えられ、Sの任意の 2 つの頂点間のすべての最短経路を評価する必要があるとしSます。
これを行う最も簡単な方法はDijkstra、 の 2 つの頂点の組み合わせごとにアルゴリズムを実行することですSが、もちろん、これは効率の点で最善の方法ではありません。
私が考えたことの 1 つは、頂点 i から頂点 j までの 1 つのパスを両方とも で評価しS、次にProcessedMapS で他の頂点を検索することでした。1 つ見つかった場合、たとえば k とすれば、i から k までの距離が既にわかっています。 . これにより、アルゴリズムの呼び出し回数が減る可能性が高くなります。しかし、私はまだレモンにもっと良い解決策があるべきだと思います.
複数のソースを追加することは役に立ちますか? Dijkstraこの機能を使用したときのクラスの動作はまだよくわかりませんでした。
ありがとうございます=）