指定されたグラフが実際にスパニング ツリーであることがわかっている場合、つまり頂点の各ペアにはそれらの間のパスが 1 つしかないことがわかっている場合、すべての頂点からすべての頂点への最短パスを見つけるにはどうすればよいですか? 最適解が欲しい。ダイクストラのアルゴリズムは知っていますが、非常に複雑です。
基本的に、1 つのソースからのすべての頂点の距離とパスを知りたいです。これがスパニング ツリーであることを考えると、これに対する最善かつ最適なソリューションは何ですか?
さらに、グラフが実際にスパニングツリーであることを考慮して、単一ソースの最短パスのアルゴリズムを複数回適用する以外に、すべてのペアの最短パスを見つける別の方法があるかどうかを教えてください。
親切に、過剰な説明を気にしてください。
最適なソリューション:
ルートとして任意の頂点を選択し、そこから深さ優先検索を実行して、ルートと番目の頂点の間の距離dist[i]をすべて計算します。ii
u任意の 2 つの頂点との間の距離vは ですdist[u] + dist[v] - 2 * dist[lca(u, v)]。ここで、はとlca(u, v)の最小共通祖先です。uv
最初のステップにはO(n)時間の複雑性があります。2 番目のステップの時間計算量は、最小共通祖先検索の実装によって異なります。線形の前処理時間でクエリごとに達成することは可能ですがO(1)(このアルゴリズムを使用: http://www3.cs.stonybrook.edu/~bender/newpub/BenderFa00-lca.pdf )、このアプローチにはかなり大きな定数があり、実装するのは非常に簡単ではありません。このソリューションはO(n)、前処理に時間がかかり (少なくとも入力を読み取る必要があるため、これ以上のことはできません)、一定の時間内にクエリに応答するため、最適です。より単純なアルゴリズムを使用して、O(log n)クエリごとの時間O(n)または前処理時間を取得することもできます。O(n log n)