求二叉樹任意兩結點的最短路徑？最好使用雙向鏈表。如果a與B連接，那么a與BB連接，那么a與a連接，然后BFS在樹上完成。復雜性O（n）為什么樹的最短路徑是BFS，圖的最短路徑是SPFA或Dijkstr

求二叉樹任意兩結點的最短路徑？

最好使用雙向鏈表。如果a與B連接，那么a與BB連接，那么a與a連接，然后BFS在樹上完成。復雜性O（n）為什么樹的最短路徑是BFS，圖的最短路徑是SPFA或Dijkstra？因為樹中沒有循環(huán)，而且任意兩點只有一條路徑，所以節(jié)點可以搜索一次。如果圖中存在循環(huán)，則意味著兩點之間可能存在多條路徑，并且可能存在一條邊權大、變權小的路徑。首先，在不考慮時間復雜度的情況下，解決了圖論中最短路徑的求解問題。這個基本問題也可以推廣到許多其他的理論或實踐問題。

最短路徑問題有一個理想的時間復雜度（<=O（n^2）），但是如果我們找到圖中任意兩點之間的距離，特別是當圖是稠密的時候，F(xiàn)loyd的O（n^3）就不比其他問題小。

Floyd的另一個優(yōu)勢是易于編寫。完成了插點、三循環(huán)、一判斷、五要素的簡單構思。Dijkstra在堆優(yōu)化和SPFA之后需要大約50行代碼。