我們可以使用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（以最優方式）查找加權有向非循環圖中從源節點到所有其他節點的最短路徑嗎？

回答

相關問題