使用 bfs 的所有顶点之间的最短路径

Question

我正在学习图论，我需要帮助。 我需要使用 bfs 计算图中所有顶点之间的最短路径的算法。我知道 bfs 是如何工作的，但我不知道“重塑”该算法来找到图中所有顶点之间的最短路径。

Answer 1

最简单的方法是每个节点重复 BFS，正如 Yerken 所说。其时间复杂度为 O( (v+e)*v )，其中 v 和 e 分别是顶点和边的数量。 O(1) < e < O(v^2), so if your graph is very dense, it is an O(v^3) algorithm. However if the graph is sparse and the complexity is O(v^2), it can be done faster with repeated Dijkstra's, because its complexity is O(v * e * log(v)) = O(v*log(v)).

或者，您可以尝试 O(v^3) 的 Floyd-Warshall 算法，但它只给出距离，而不给出路径。

Answer 2

如果你想找到顶点之间的最短路径，可以通过 Floyd Warshall 算法来完成。它是一种图分析，可用于查找图中所有节点对之间的最短路径。