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

求二叉樹(shù)任意兩結(jié)點(diǎn)的最短路徑？

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

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

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