1

我有加权无向图。我需要以尽可能小的成本找到生成树，以便 A 点和 B 点之间的距离尽可能低。例如，我有这个图：graph。A 和 B 之间的最小距离为 2。最小生成树看起来像这样。但这会使 A 和 B 之间的距离 = 3。

现在我正在这样做：

  1. 使用 BFS 查找图中 AB 之间的距离。
  2. 使用 DFS 从步骤 1 中找到 AB 之间的所有路径。
  3. 从步骤 2 中的每条路径生成生成树。
  4. 比较它们并获得最小的一个。

一切都很好，直到我得到 AB 距离 = 12 的图表。第二步然后花费太多时间。有没有更快的方法来做到这一点？谢谢。

4

2 回答 2

2

解决这个问题的最快/最有效的方法是使用Dijkstra 的最短路径算法。这是一个贪心算法，具有以下基本结构：

1-图上的所有节点都以“无限”距离开始

2-从您的第一个节点（示例中的节点 A）开始，并跟踪每个边权重以从该节点 A 到其每个邻居。

3-选择最短的当前边并跟随它到你的下一个节点，我们暂时称它为节点 C

4-现在，对于 C 的每个邻居，将当前距离（如果适用，包括无穷大）与 A 到 C 的边和 C 到当前邻居的最短边的总和进行比较。如果它比当前距离短，则将其更新为新距离。

5-继续这个过程，直到所有节点都被访问并且您到达您正在寻找最短路径的节点（即您的示例中的 B）

这是找到两个节点之间最短路径的一种非常有效的方法，运行时间为O(V^2)，而不是 如上所述的O(nlogn) 。如您所见，通过将其设为贪心算法，我们不断地根据可用的本地信息选择最佳解决方案，因此我们永远不必回头改变我们的决定。

这也消除了对您示例中的 BFS和DFS 的需求。希望这可以帮助！

于 2019-10-28T03:33:27.533 回答
1

虽然您的第二步是正确的，但我认为问题在于您进行了太多操作。

您正在同时进行 BFS 和 DFS，这将非常昂贵。相反，我建议做的是使用几种不同的遍历技术之一，这将最大限度地降低计算成本。

这是寻找最短路径的常见问题，流行的解决方案之一是 Dijkstra 算法。这是一篇阐述该主题的文章。https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

简而言之，这个算法的作用，就是以A为起点，然后生成最小生成树，直到B点被命中，那么A到B只有一条路径，这就是最短路径.

这个和你的算法都在 O(nlogn) 中运行，但实际上这个解决方案可以被认为是运行单个 BFS 而不是 BFS 和 DFS。

于 2018-11-13T02:36:17.420 回答