我们可以使用BFS（以最优方式）查找加权有向非循环图中从源节点到所有其他节点的最短路径吗？

我知道它可以在O（V + E）中使用拓扑排序完成。但我认为它也可以使用BFS以相同的复杂度完成。我们可以使用BFS（以最优方式）查找加权有向非循环图中从源节点到所有其他节点的最短路径吗？

2017-04-23 Aditya Joshee

你能详细说明一下你的意思吗（以最优方式）？如果你的意思是复杂性，那么是的。拓扑排序是DFS的应用，这就是为什么它具有O（V + E）的复杂性。我认为询问“我们可以使用BFS做拓扑排序吗？”更自然。这个问题已经被问到。 – Abdulhakeem

我的意思是我们可以只使用BFS而不是以拓扑顺序访问节点。 –

除了它是一个DFS运行外，拓扑排序没有任何意义。然后，当每个顶点完成后，将它放到链表的前面。它的运行时间为O（V + E）。正如我之前所说的，我认为在这里更自然地问“我们可以使用BFS进行拓扑排序吗？”。这已经被问及和回答。

如果你的意思是纯粹的BFS，那么我会说不。看看这个example。拓扑排序是所有顶点的线性排序，因此如果图G包含边（u，v），则u在排序中出现在v之前。在这个例子中你可以看到从c到d有一条边，但是d出现在c之前。我认为你可以更新BFS来查找拓扑排序，但它又像运行DFS一样复杂。我建议你看看这篇文章Using BFS for topological sort

来源

2017-04-25 16:42:24 Abdulhakeem

让我们忘了一段时间的拓扑排序。如果我使用广度优先遍历DAG，从一个源节点s开始，那么我可以通过维持一个距离数组（初始化为无穷大）并在O（V + E）时间内找到所有其他节点的最短距离，并在我们得到的值小于当前存储的节点值。因此，回到我原来的问题，是不是这种方法具有与使用拓扑顺序遍历DAG中的节点以找到最短路径相同的复杂性？ –

我们可以使用BFS（以最优方式）查找加权有向非循环图中从源节点到所有其他节点的最短路径吗？

回答

相关问题