-4

隣接行列で表される無向グラフがあります。

高効率のコードが必要です。関数は true または false を返すだけです。

そして、ダイクストラのアルゴリズムが機能することはわかっています。最短経路は必要ないと思います。隣接行列は次のとおりです。

a[i][j] = 1 or -1

他の値はありません。

4

2 に答える 2

0

2 つのポイントが接続されているかどうかだけを知りたい場合は、http://en.wikipedia.org/wiki/Disjoint-set_data_structureを使用すると、期待どおりに迅速に処理できると思います。独自のセット内のすべてのポイントから開始し、2 つのポイント間のリンクごとに、それらのポイントが属する 2 つのセットを結合します。

于 2012-08-12T04:12:30.860 に答える
0

申し訳ありませんが、マトリックスに 0 と 1 しか含まれていないことに気付きませんでした。

クエリを 1 回だけ実行する場合は、DFS または BFS の方が優れている可能性があります。O(|V|+|E|)

双方向パスならDisjoint-set data structure(ウィキペディア参照) が有効！

  • シングルソースかマルチソースか?
  • シングルクエリかマルチクエリか?

クエリが 1 つしかない場合は、すべての単一ソース最短パス アルゴリズムで問題ありません。お気に入り：

  • ベルマンフォードO(|V||E|)
  • ダイクストラO(|V|^2)
  • ダイクストラ + ヒープΘ((|E|+|V|)log|V|)
  • SPFA (Bellman-Ford キューを使用)
  • ...

問い合わせが多い場合は検討

  • Floyd-Warshall アルゴリズムO(|V|^3)
于 2012-08-12T02:49:49.830 に答える