轉(zhuǎn)自：http://apps.hi.baidu.com/share/detail/17558221
既然是解決尋找兩點之間最短路徑的的問題。我們自然會想一個描述兩點之間最短路徑特征的命題。

如果在點A和C之間存在一條最短路徑AC，并且在AC上有個點B，那么，沿這條路徑產(chǎn)生的路徑AB，是點A到點B的最短路徑。

像這張圖，如果這條路徑是A到G的最短路徑，那么AF路徑就一定也是A到F的最短路徑。

用反證法證明的話，可以這么說。如果存在一條更短的A到F的路徑，那么我們完全可以從A走更短的路徑到達F，然后再從F到達G，那么產(chǎn)生的路徑就比AG要短，這顯然和AG是最短路徑這個前提矛盾。故AF就一定是最短路徑啦。

同理，我們還能推出，AB，AC，AD，甚至BD，BE都是最短路徑，這個圖中任意兩點沿這個路徑所產(chǎn)生的路徑，都是最短路徑。當(dāng)然，這個最短路徑不是唯一的，這只是其中一條。

利用這個數(shù)學(xué)原理，我們可以在尋路過程中，率先找到起點到某點的一條最短路徑，那么之后的所有尋路都基于這個最短路徑之上，而不必考慮起點到這個點的其他路徑。這樣的方法能剔除大量無謂的路徑，減少時間和空間的壓力。

那么如何率先找到起點到某點的最短路徑呢？這里用到數(shù)據(jù)結(jié)構(gòu)里面的一種廣度優(yōu)先搜索的方法對圖進行搜索。

廣度優(yōu)先搜索按照從起點到其他點的路徑的長度，從短到長一層一層搜索。當(dāng)某個點第一次被搜索到，那么所搜索的那個路徑就一定是一條最短路徑了。這個講起來有點抽象，下面我們用一張3*3的地圖來演示下搜索的過程。

這張地圖中，F(xiàn)為障礙物，A是起點，I是終點。每個格子，即一個結(jié)點，有三部分和搜索有關(guān)的屬性。第一個是指向和這個節(jié)點相鄰的結(jié)點的一系列引用（圖中黑色箭頭表示）。第二個是指向母結(jié)點的引用（圖中紅色箭頭表示），在未開始搜索之前，這個屬性是空的。第三個就是一個布爾值，表示結(jié)點是否是可被搜索的，障礙物默認是不可被搜索的，沒有人會產(chǎn)生一個經(jīng)過障礙物的路徑吧，所以這個搜索直接忽略。

將地圖連接好之后，我們會產(chǎn)生一個圖（此圖為數(shù)據(jù)結(jié)構(gòu)里面的概念），當(dāng)然，我們也能把這個圖看成是一個根節(jié)點是起點，元素能重復(fù)的無限深度的樹。

然后我們就開始搜索，首先，從A出發(fā)，我們能到B和D，由于B和D是第一次被搜索到，故AB和AD必然是最短路徑（這個是不爭的事實，他們一步就到了，其他路徑皆是繞圈子）。

恩，很好，那么接下來我們就把B和D的指向母結(jié)點的引用（上面提到的結(jié)點的第二部分屬性，也就是地圖中畫出的紅色箭頭）指向A，表示從起點到達B和D的最短路徑是從A那過來的，這樣就把路徑儲存下來了。

然后，將B和D設(shè)為不可搜索，表示B和D的最短路徑已經(jīng)產(chǎn)生了，要是下面要是還搜他們，那么產(chǎn)生的路徑一定沒這個短，因為搜索的順序是從短到長的嘛。所以就沒有必要對他們搜索了。

最后，將B和D存入第二層的臨時數(shù)組，第二輪的搜索就要從B和D開始了！

第二輪，首先，從B開始搜索，像剛才從A開始一樣。我們發(fā)現(xiàn)，B的子節(jié)點有三個，其中A被鎖定了（藍色表示，它的子節(jié)點由于不參與搜索，就暫時忽略不畫），所以直接忽略A。

然后是E和C，發(fā)現(xiàn)者兩個沒有被鎖定，那么它們就是第一次出現(xiàn)咯（因為第一次出現(xiàn)后就要被鎖定，所以沒鎖定的就是第一次出現(xiàn)）。恩，把他們像剛才處理B和D一樣，設(shè)置路徑，然后鎖定，再存入第三層的臨時數(shù)組。

B的子節(jié)點處理完了，然后是D的子節(jié)點。A是鎖定的忽略，E剛才在處理B的子節(jié)點的時候被鎖了，所以也忽略。恩，G第一次出現(xiàn)，把它處理了存入第三層數(shù)組，這樣，第三層就全部處理完了。下面進入第三輪搜索。

第三輪中，只有H新來的，其他均是老面孔。H存入第四層數(shù)組，接下來進入第四輪搜索。

G是老面孔，I是新來的，而且！I就是我們所要的終點。。OK！，搜索就這樣結(jié)束了！

我們沿著I的指向母結(jié)點的引用，I-H-E-B-A，到達起點，這個就是我們要找的路徑。

這里，我們不止可以找到起點到終點的最短路徑。在搜索過程中，我們已經(jīng)建立了一個從起點出發(fā)，到任何點的最短路徑的樹。從任何點出發(fā)，沿著指向母結(jié)點的引用走到起點，都能產(chǎn)生最短路徑。