最短経路を見つけるための効率的な方法で、5GBを超える重み付けされていない有向グラフをMySQLデータベースに保存しようとしています。現在、列ソースとコンマターゲット（コンマで区切られている）を含む単一のテーブルに格納されていますが、これは方法ではないと感じているので、頂点とテーブルを含むテーブルに変換することを計画していますエッジ付き。
2つの質問があります。
- グラフを保存する最良の方法は何ですか？
- どの最短経路アルゴリズムを使用する必要がありますか？
質問する
1379 次
2 に答える
2
2 つのテーブルが必要です。1 つはノード用、もう 1 つはエッジ用です。エッジ テーブルには、source_node_id と dest_node_id が必要です。このようにして、エッジ テーブルに対して簡単にクエリを実行し、ダイクストラ アルゴリズムで使用されるすべての出力ノードを取得できます。
簡単な Dijksra アルゴリズムの説明については、 http ://www.sce.carleton.ca/faculty/chinneck/po/Chapter8.pdf を参照してください。
于 2013-02-03T17:20:05.523 に答える
0
密なグラフを格納するもう 1 つの非常に効率的な方法 (疎なグラフはあまり効率的ではありません) は、隣接行列を使用することです。ここにそれを説明するリンクがあります -
ここで、行列を MySQL データベースに保存するには、rowid を行の頂点 ID として使用する必要があります (頂点の ID を 1、2、... と仮定すると)。列は、通常の頂点名または頂点 ID にすることができます。頂点名を ID にマップするテーブルを保持できます。
直面する問題の 1 つは、列の最大数です。マトリックスが大きすぎる場合は、列を複数のテーブルに分割する必要がある場合があります。必要なノードからテーブルの名前をすぐに通知するインデックス スキーム/ハッシュ スキームがある場合、クエリは比較的高速になります。
そして、最短経路については、他の人が述べたように、ダイクストラ アルゴリズムが最適な最短経路検索アルゴリズムです。
于 2015-07-06T12:48:03.780 に答える