本人是國中蒟蒻，還有3天就要考CSP了，結果發現Dijkstra的優化還不會，寫篇經驗當作複習
Dijkstra 是計算單源最短路的算法，其時間複雜度在 \(O(n^2)\)，比 Floyd 快一個指數級。該算法其實是一種貪心的思想（藍白點），原理比較好了解。
Dijkstra題目：
【洛谷】單源最短路徑（标準版）
【洛谷】單源最短路徑（弱化版）
首先，我們先要明确 Dijkstra 最重要的邏輯：在同一條路徑上，經過的邊越多，走的距離就越遠
Dijkstra 的算法思想，就是一開始将起點到起點的距離标記為 \(0\)(<code>dis[s] = 0</code>, 其中 <code>s</code> 為起點)，而後進行 <code>n</code> 次循環，每次找出一個到起點距離 <code>dis[u]</code> 最短的點 <code>u</code>，将它從藍點變為白點。随後枚舉所有的藍點 <code>vi</code>，如果以此白點為中轉到達藍點 <code>vi</code> 的路徑 <code>dis[u]+w[u][vi]</code> 更短的話，就将它作為 <code>vi</code> 的“更短路徑” <code>dis[vi]</code> （此時還不确定是不是vi的最短路徑）。
如果這段文字你沒法了解，那就請看下面幾張圖：
我們規定：藍點為未被操作過的點，白點為已操作過的點。
算法開始時，作為起點的 1 号點被初始化為<code>dis[1] = 0</code>，其他的點<code>dis[i]</code>為無窮大。
第一輪循環找到dis[1]最小，将1變成白點。
對所有的藍點做出修改，使得 <code>dis[2]=2,dis[3]=4,dis[4]=7</code>。
第二輪循環找到 <code>dis[2]</code> 最小，将 2 變為白點。與此同時，對所有的藍點做出修改，使得 <code>dis[3] = 3, dis[5] = 4</code>。
第三輪循環找到dis[3]最小，将3變成白點。對所有的藍點做出修改，使得<code>dis[4] = 4</code>。發現以3為中轉不能修改5，說明`3 不是5的最後一個中轉點。
以此類推，進而找到最短路徑。
總結下來：如果找到一個中轉點<code>i</code>使該點與<code>s</code>點的路徑更短，就更新<code>dis[i]</code>
Dijkstra無法處理邊權為負的情況，例如上圖這個例子。
2到3的邊權值為-4，顯然從起點1到3的最短路徑是-2（1→2→3），但是dijskstra在第二輪循環開始時會找到目前dis[i]最小的點3，并标記它為白點。
這時的dis[3]=1，然而1卻不是從起點到點3的最短路徑。因為3已被标記為白點，最短路徑值dis[3]不會再被修改了，是以我們在邊權存在負數的情況下得到了錯誤的答案！
（以上推導過程選自《資訊學奧賽一本通》）
想明白思路，那麼接下來就可以上代碼了。該代碼是洛谷P4479題，一道圖論的模闆題。
不要抄代碼！！小心棕名！！
有錯誤請指出勿噴