第十四章 最短路徑

　　“唰唰！”

　　牛仔從大樹上面跳下來(lái)。

　　然后，他看見(jiàn)了倒在地上，奄奄一息的小機(jī)器人羅比。

　　“哥們，發(fā)生啥事了？”

　　楊成趕緊爬起來(lái)，毫發(fā)無(wú)損，看了看小機(jī)器人，臉上很是詫異。

　　就在這時(shí)，羅比開(kāi)口了，它的聲音很微弱。

　　“主人...”

　　“羅比的尋路邏輯被破壞了...”

　　“如果想讓羅比帶你們回家...”

　　“請(qǐng)先編寫代碼修復(fù)...”

　　楊成聽(tīng)到這里，已經(jīng)有了些眉目。

　　這個(gè)關(guān)卡敢情是考查尋路算法??！

　　對(duì)于要找到地圖中，兩個(gè)點(diǎn)之間的路徑，有一種簡(jiǎn)單而粗暴的做法。

　　從出發(fā)點(diǎn)使用深度優(yōu)先遍歷，如果達(dá)到了終點(diǎn)，就終止并返回路徑。

　　它的實(shí)現(xiàn)方式很簡(jiǎn)單，但是有兩點(diǎn)不足：

　　1.效率低下

　　2.它找到的路徑不一定是最短路徑，很有可能會(huì)繞遠(yuǎn)路。

　　第二點(diǎn)尤其糟糕，繞遠(yuǎn)路白費(fèi)力氣吶...

　　所以，這個(gè)問(wèn)題應(yīng)該是尋找圖中兩點(diǎn)間的最短路徑。

　　楊成很快想到了，有一種經(jīng)典的算法：

　　迪杰斯特拉最短路徑算法。

　　還有另一種簡(jiǎn)潔的解法，廣度優(yōu)先遍歷。

　　它們都很合適。

　　但從效率上來(lái)說(shuō)，還是有細(xì)微的差別。

　　迪杰斯特拉算法經(jīng)過(guò)優(yōu)化后的時(shí)間復(fù)雜度是：

　　O（N*logN）

　　廣度優(yōu)先遍歷是O（N）。

　　然后空間效率，在一般情況下，迪杰斯特拉需要的額外空間更多。

　　（Breadth-First Search）

　　就是你了，BFS！

　　它足夠簡(jiǎn)單，實(shí)現(xiàn)方便，而且效率也不會(huì)很低...