Dijkstraのアルゴリズムのテストグラフを構築する戦略？

Question

私は最近、Dijkstraのアルゴリズムを実装してJavaを実践しました。私は今、ランダムなテストグラフを作成する方法を検討しています（片方向エッジで）。

現在、私はナイーブな方法を使用しています。ノードは2次元空間（xとyは0〜MAX_SPACE定数の間の符号なし整数）の任意の場所に作成されます。エッジは、ノードを接続するためにランダムに作成されるため、各ノードのアウトディートは少なくとも1（最大MAX_DEGREE）です。インシデントは強制されません。次に、セット内の最初と最後のノードの間のパスを検索します。これは接続されている場合と接続されていない場合があります。

より現実的な状況では、ノードは2d空間での近接度に比例して接続される可能性があります。そのプロパティを持つランダムなテストグラフを作成するための良い戦略は何ですか？

NOTES

私は主に手で描かれたと確認することができ、グラフを構築するために、これを使用しますが、より大きなグラフにスケーリングすることは考慮されます。

戦略は簡単に以下の定数をサポートするように変更する必要があります（そしておそらく他の人を - あなたは何か面白いものを考えるなら、私に知らせて）：

• MIN_NODES、MAX_NODES：グラフのサイズの範囲
• つながり：平均出次数
• PROXIMITY：あなたは異なるランダムで見ることによって開始することができ、近位のノード

Answer 1

を接続することを好むに与えられる重みJUNG（Javaライブラリ）で利用可能なグラフ・ジェネレータ：

• Barabasi Albert Generator - シンプルな進化スケールフリーランダムグラフ生成。各時間ステップで、新しい頂点が作成され、「優先的な取り付け」の原則に従って既存の頂点に接続され、それにより、より高い度合いの頂点が取り付けのために選択される確率が高くなる。

• Eppstein Power Law Generator - べき乗級数分布を持つ無向グラフを生成するグラフジェネレータ。

に利用できる様々な他の発電機があります - Python用See Listing Here

はまた、多くのグラフジェネレータを提供NetworkXライブラリがある - Listed Here

これらの発電機の多くを使用すると、サイズを指定することができ、あなたは小さく始めてそこから行くことができます。