私はグラフ理論を学んでいて、アルゴリズムの問題にコードを書き込もうとしています。この問題には、n人のグループが関係しており、各グループはメンバーの 1 人と少なくとも 1 つの共通の友情を持っています。問題は、2 人の間の最短の友情リンクを見つけることです。最短の友情リンクには、含まれる人数が最も少なくなります。例えば; A と B は相互の友人であり、B と C は相互の友人であり、A と C も相互の友人である場合、AC と ABC は A と C の間の友情リンクですが、AC はより少ない個人が関与するため、より短いと見なされます。
この場合、どのグラフ理論アルゴリズムが適用されるかを知りたいです。また、グラフ理論に関する優れた無料のインターネット ドキュメント (wiki 以外) を推奨していただければ幸いです。
2 つのノードの最短パスの重み付けされていない問題については、BFSで実行できます。実装が難しく、効率の悪いダイクストラのアルゴリズムは必要ありません。
BFS の主な問題はスペース効率であることに注意してください。BFS はスペースで実行されるため、 Iterative Deepening DFSO(|V|)と呼ばれる DFS とのトレードオフで部分的に解決できます。これも最適ですが、消費するスペースが少なくなります (余分な時間がかかります)。
そうではないようですが、ターゲットにどれだけ近いかを評価できる場合は、優れたヒューリスティック関数が与えられているA* Algorithmを使用すると、より高速に実行される可能性があります。
また、注意: すべてのユーザー間の最短距離が必要な場合は、Floyd-Warshall のアルゴリズムを使用できます。