作爲運行Dijkstra算法的結果的生成樹？

Question

只需要確認一下： 當我在圖上運行Dijkstra算法時，最後我會有一棵生成樹嗎？ （不一定是最小生成樹）

所以，Dijkstra算法之間的差異PRIM /克魯斯卡的後兩種算法將返回一個最小生成樹？

感謝

Answer 1

你是正確的，有一個條件 - 圖應該從源頭上生成樹（即 - 圖中每個頂點v具有從給定的源路徑）。
此外，正如@Henry所述 - 您應該繼續算法，直到找到所有頂點的路徑，並且一旦達到目標就不會「停止」。

另請注意，Dijkstra的算法（和一般 - 最短路徑求解器）是針對有向圖定義的，而MST通常是針對無向圖的。 （注意，通過簡單地爲無向圖中的每個邊{u，v}添加（u，v）和（v，u），容易將每個無向圖定義爲有向圖）