單源最短路徑問題
給定加權(quán)有向圖G=(V,E,W)议惰，每條邊的權(quán)值w為非負數(shù)意狠，表示兩個頂點間的距離悲酷。
源點s∈V套菜。
求：從s出發(fā)到其他各個頂點的最短路徑。
如上圖所示设易，以1為源點逗柴，計算到其余各個頂點的最短距離（我已用紅線標出）。下面列出了最終解：
源點：1
1->6->2 : short[2] = 5
1->6->2->3 : short[3] = 12
1->6->4 : short[4] = 9
1->6->5 : short[5] = 4
1->6v : short[6] = 3
Dijkstra算法相關(guān)概念
S集合：當從s到x（x ∈V ）的最短路徑找到時顿肺，則x ∈S戏溺。當所有頂點都進入S集合時，算法結(jié)束挟冠。
初始：S=｛s｝于购，當S=V時算法結(jié)束。
從s到u相對于S的最短路徑：指從s到u且僅經(jīng)過S中頂點的最短路徑知染。
dist[u]:從s到u相對于S的最短路徑長度
short[u]:從s到u最短路徑的長度（算法最終解）
dist[u] ≥ short[u]
Dijkstra算法采用貪心算法模式肋僧，算法過程就是通過計算dist[u],不斷擴充S集合，同時dist[u]會不斷優(yōu)化改善控淡，直到dist[u] = short[u]嫌吠，并將其放到S中，當所有頂點都放入S集合時掺炭，算法結(jié)束辫诅。
算法設計思想
輸入：加權(quán)有向圖G=(V,E,W)
? ? ? ? ? V={1,2,…,n}, s=1
輸出：從s到每個頂點的最短路徑
1.初始S=｛1｝
2.對于u ∈V-S,計算1到u的相對于S的最短路，長度為dist[u]
3.選擇V-S中dist值最小的那個頂點涧狮，加入S炕矮。
4.繼續(xù)上述過程，直到S=V為止者冤。
實例
輸入：G=(V,E,W)肤视，源點1
????????? V={1,2,3,4,5,6}
初始S集合只有1，計算直接從1能到達的頂點的距離涉枫，其他不能從1號頂點直接到達的頂點都記為無窮大邢滑。此時從dist[u]里找出最短距離的頂點（6號），并將其放進S集合愿汰。
? S={1}
? dist[1] = 0
? dist[2] = 10
? dist[6 ] = 3
? dist[3] = ∞
? dist[4] = ∞
? dist[5] = ∞
當把6號頂點放進S集合后困后，經(jīng)由6號頂點出發(fā)到達的頂點的最短距離可能會被優(yōu)化更新，因為該算法的思想很“貪心”衬廷，誰更短我要誰摇予！比如1->6->2要比1->2距離更短，所以dist[2]被更新為5吗跋，從專業(yè)術(shù)語上講侧戴，這個“更新”過程叫做松弛，其他點同理。然后從dist[u]里找出最短的路徑的那個頂點（5號）救鲤，并放進S集合里。
? S={1,6}
?dist[1] = 0
?dist[6] = 3
? dist[2] = 5
? dist[4] = 9
? dist[5] = 4
? dist[3] = ∞
后面的操作步驟其實就是重復上面的操作秩冈。即當S集合里有個新的頂點后本缠，就可能會更新其他點的最短距離，更新一遍后入问，找出當前最短距離的dist[u]丹锹，并將該頂點放進S集合。后面不重復闡述芬失。
? S={1,6,5}
?dist[1] = 0
?dist[6] = 3
? dist[5] = 4
? dist[2] = 5
? dist[4] = 9
? dist[3] = ∞
? S={1,6,5,2}
?dist[1] = 0
?dist[6] = 3
? dist[5] = 4
?dist[2] = 5
? dist[4] = 9
? dist[3] = 12
? S={1,6,5,2,4}
?dist[1] = 0
?dist[6] = 3
? dist[5] = 4
?dist[2] = 5
?dist[4] = 9
? dist[3] = 12
? S={1,6,5,2,4,3}
?dist[1] = 0
?dist[6] = 3
? dist[5] = 4
?dist[2] = 5
?dist[4] = 9
?dist[3] = 12
當有向圖中的所有頂點都進入了S集合后楣黍，算法結(jié)束，此時的dist[u]的值其實就是最初我們找出的那個最終解short[u]棱烂，所以租漂，算法結(jié)束時，dist[u]=short[u],得到最終解颊糜。
