迪傑斯特拉(Dijkstra)算法

 迪傑斯特拉算法是單源點最短路徑算法之一。本文力圖能夠不用任何圖示和程式說清楚迪傑斯特拉算法，來幫助大家了解這個算法。

首先說說什麼叫單源點最短路徑問題。顧名思義首先得有個源點，說白了就是出發點。單源點最短路徑問題就是求從一個點出發到圖中所有點的最短路徑。通俗地說就是從一個地方出發到所有地方的最短的距離。例如從北京到上海、廣州、深圳、長春、沈陽、天津怎麼走最近。顯然從北京到長春可以這麼走：北京-沈陽-長春。

那麼怎麼能求出一個點到所有點的最短路徑呢。那麼這些方法中有一種是迪傑斯特拉發明的就叫做迪傑斯特拉算法。他是這樣想的：從一點出發先算出到所有點的直達距離。然後找一個最近的作為中轉站，再求出在準許走中轉站的情況下源點到其他所有點的距離，如果比原來小了就記錄下來。然後重複剛才的步驟再添加一個中轉站。舉個例子：假如你要從北京去德惠，德惠市是長春周邊的一個小城市。北京沒有直達的火車。那怎麼辦呢你可以先坐火車去長春再做汽車去德惠。可惜正趕上春運啊，北京直達長春的車沒有了。那咋辦呢，可以先坐火車去沈陽，沈陽倒車去長春，長春坐汽車去德惠。其實這樣的例子在生活中我們總會遇到，說白了這就是迪傑斯特拉算法。通過添加中轉站來找到最短路徑。在上例中北京到長春和德惠的距離一開始都是無窮大，就是不能直達。但是可以直達沈陽。當把沈陽當做中轉站後到達長春就成為了可能不過還是到不了德惠。添加長春為中轉站後就可以到德惠了。

上面說的不知道大家能明白嗎，有人可能說怎麼沒提距離呢，恩，能到就是1不能就是無窮大，實際和權值是具體數值一樣。置于程式怎麼寫和數學原理我想網上有很多了，不過算法的關鍵再與了解。