bfsを使用するすべての頂点間の最短経路

Question

私はグラフ理論について学んでおり、助けが必要です。 bfsを使ってグラフ内のすべての頂点間の最短経路を求めるアルゴリズムが必要です。私はbfsの仕組みを知っていますが、グラフ内のすべての頂点間の最短経路を見つけるアルゴリズムを「リメイク」することは知られていません。

Answer 1

Yerken氏によると、最も簡単な方法は、各ノードのBFSを繰り返すことです。その時間の複雑さはO（（v + e）* v）であり、ここでvとeは頂点と辺の数です。 O（1）< e < O（v^2）なので、グラフが非常に密であればO（v^3）アルゴリズムです。しかし、グラフが疎で複雑さがO（v^2）であれば、その複雑さはO（v * e * log（v））= O（v * log（v））であるため、 ）。

また、Floyd-WarshallアルゴリズムをO（v^3）で試すこともできますが、パスではなく距離のみが得られます。