圖的應(yīng)用：最短路徑

上篇文章的最小生成樹有沒有意猶未盡的感覺呀？不知道大家掌握得怎么樣，是不是搞清楚了普里姆和克魯斯卡爾這兩種算法的原理了呢？面試的時(shí)候如果你寫不出，至少得說出個(gè)大概來吧，當(dāng)然，如果你是要考研的學(xué)生，那就要深入的理解并且記住整個(gè)算法的代碼了。

什么是最短路徑

今天我們學(xué)習(xí)的是圖的應(yīng)用中另外一個(gè)經(jīng)典的問題，也就是 最短路徑 的問題。這個(gè)問題和最小生成樹是不同的，最小生成樹的要求是要連通所有的結(jié)點(diǎn)，并且走得是權(quán)值最小的那條路線。而最短路徑則是指的從某個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)中權(quán)值最小的那條路徑。這條路徑不一定是包含在最小生成樹中的，所以它們并沒有太大的聯(lián)系。

從這張圖來看，我們從結(jié)點(diǎn) 1 到結(jié)點(diǎn) 2 的最短路徑是 2 ，這個(gè)很明顯。那么從結(jié)點(diǎn) 1 到結(jié)點(diǎn) 3 呢？可不是直接的中間那個(gè)權(quán)值為 6 的路徑，而是走 1->2->3 這條路徑，也就是權(quán)值加起來為 5 的這條路徑。

然后我們?cè)賮砜唇Y(jié)點(diǎn) 3 ，它到結(jié)點(diǎn) 1 最短路徑應(yīng)該是走 3->4->1 這條路徑，也就是權(quán)值為 6 的這條路徑，而不是中間的那條直線的權(quán)值為 7 的路徑。

沒錯(cuò)，這就是最短路徑的概念了。在最短路徑中，我們一般會(huì)解決單向圖的問題，但實(shí)際生活中呢？最典型的地圖相關(guān)的應(yīng)用其實(shí)是都是雙向圖的。不過這并不影響我們的學(xué)習(xí)，我們可以把這個(gè)示例圖中的結(jié)點(diǎn)看成是城市火車站點(diǎn)，就算是連接結(jié)點(diǎn) 1 和結(jié)點(diǎn) 3 的火車線路，也不一定來去的時(shí)間都是相同的。比如說從長沙到北京的 Z2 次火車全部運(yùn)行時(shí)間為14小時(shí)42分，而回來的 Z1 次則是14小時(shí)10分。那么我們是否可以選擇其它的火車，比如有趟火車從長沙到石家莊可能只需要8小時(shí)，然后從石家莊到北京只需要2小時(shí)，這樣我們選擇這條線路的總時(shí)間就只需要10小時(shí)了（當(dāng)然，這只是例子，大家在非高鐵的情況下肯定還是