算法原理
Dijkstra算是一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法。簡單來理解，有兩個主要的步驟：
- 比較：當(dāng)前（這個可能會在下一步更新）各個點到源點的距離，擁有最短距離的點（假設(shè)為v2）的當(dāng)前路徑即v2到源點的最短路徑
-
更新：對于沒有求出最短路徑的點，如果通過上一步求出的最短路徑+彼此連接的弧長度小于當(dāng)前該點到源點的距離，則將新的路徑作為該點的最短路徑
重復(fù)1、2操作，直到求出所有點的最短路徑。
算法實例
問題：給定帶權(quán)有向圖G和源點v0，求v到G中其余各頂點的最短路徑
以上這張表就是求解的整個過程：
其中，vj：當(dāng)前循環(huán)求出vj到源點的最短距離
S：已經(jīng)求出最短路徑的集合
1. 第一次循環(huán)
豎著看表格
v1和v0沒有路徑，距離為無限大;
v0和v2的弧長為10，距離為10;
同理， v3為無限大，v4為30，v5為100
這5個點到源點距離最短的是v2，那v2的最短路徑就求出來了，路徑就是v0直接到v2
2. 第二次循環(huán)
剩余v1,v3,v4,v5沒有求出來
因為新求出最短路徑的v2到v1沒有弧連接，因此，v0-v2這條最短路徑對于v1沒有影響，不更新
v3到v0的距離本來為無限大，有了v0-v2的路徑之后，v0-v2-v3的距離和為60，比原來短，更新v3的路徑
同理，v2到v4沒有路徑（也可以看成是無限大），不更新；到v5沒有路徑，不更新
現(xiàn)在，v1,v3,v4,v5中路徑最短的是v4，那v4到v0的最短路徑就求出來，就是v0-v4
3. 第三次循環(huán)
剩余v1,v3,v5沒有求出來
v4到v1沒有連接弧，不更新，依然為無限大
v0-v4-v3的路徑總長度為50，比之前的60短，更新v3的當(dāng)前最短路徑為v0-v4-v3，長度為50
v0-v4-v5的路徑總長度為90，比之前的100短，更新v5的當(dāng)前最短路徑為v0-v4-v5，長度為90
現(xiàn)在，v1,v3,v5中路徑最短的是v3，那v3到v0的最短路徑就求出來，是v0-v4-v3
4. 第四次循環(huán)
剩余v1,v5沒有求出來
v3到v1沒有連接弧，不更新，依然為無限大
v0-v4-v3-v5的路徑總長度為60，比之前的90短，更新v5的當(dāng)前最短路徑為v0-v4-v3-v5，長度為60
現(xiàn)在，v1,v5中路徑最短的是v5,那v0到v5的最短路徑就是v0-v4-v3-v5
5. 第五次循環(huán)
剩余v1沒有求出來，v5到v1沒有路徑，不更新。那v0到v1的最短路徑就是沒有路徑
C語言描述的Dijkstra算法
看到這里，你懂了嗎？想當(dāng)初大二學(xué)習(xí)的時候就是因為這個算法被老師表揚了一番，可開心了。
