第十四章 最短路徑
“唰唰！”
牛仔從大樹上面跳下來。
然后，他看見了倒在地上，奄奄一息的小機器人羅比。
“哥們，發(fā)生啥事了？”
楊成趕緊爬起來，毫發(fā)無損，看了看小機器人，臉上很是詫異。
就在這時，羅比開口了，它的聲音很微弱。
“主人...”
“羅比的尋路邏輯被破壞了...”
“如果想讓羅比帶你們回家...”
“請先編寫代碼修復...”
楊成聽到這里，已經(jīng)有了些眉目。
這個關(guān)卡敢情是考查尋路算法啊！
對于要找到地圖中，兩個點之間的路徑，有一種簡單而粗暴的做法。
從出發(fā)點使用深度優(yōu)先遍歷，如果達到了終點，就終止并返回路徑。
它的實現(xiàn)方式很簡單，但是有兩點不足：
1.效率低下
2.它找到的路徑不一定是最短路徑，很有可能會繞遠路。
第二點尤其糟糕，繞遠路白費力氣吶...
所以，這個問題應該是尋找圖中兩點間的最短路徑。
楊成很快想到了，有一種經(jīng)典的算法：
迪杰斯特拉最短路徑算法。
還有另一種簡潔的解法，廣度優(yōu)先遍歷。
它們都很合適。
但從效率上來說，還是有細微的差別。
迪杰斯特拉算法經(jīng)過優(yōu)化后的時間復雜度是：
O（N*logN）
廣度優(yōu)先遍歷是O（N）。
然后空間效率，在一般情況下，迪杰斯特拉需要的額外空間更多。
?。˙readth-First Search）
就是你了，BFS！
它足夠簡單，實現(xiàn)方便，而且效率也不會很低...