algorithm - 重み付けされていない無向グラフから正確に長さ l のエッジを持つ別のグラフを計算する

Question

V元の重みなし (長さ 1 のエッジを想定) および無向グラフ のすべての頂点からエッジ長 l でのみ取得できる頂点を特徴とする別のグラフを作成する方法は何ですかG=(V,E)。V各頂点からパス長 l のすべての頂点が見つかるまで、各頂点で深さ優先検索を使用して、各ブランチから各ブランチを検索するだけのソリューションを思いつきました。O(V^(l+1))もちろん、これは実行時間を与えますが、これは最適な解決策ではありません。より良い漸近ランタイムでより良い解決策を見つけるのを手伝ってくれる人はいますか?

Answer 1

行列表現を使用するFloyd-Warshallアルゴリズムを使用できますが(@Hammar が提案したようにO(V^3)) l、. 行列の累乗の代わりに、lノードを順番に挿入し、最短経路への影響を判断することで、すべての距離を判断します。