在現實生活中，我們常常需要處理最短路徑問題
例如：
下面是一張網路圖，你是否能告訴我 終端機1 ~ 終端機7 的最短路徑？
為解決這個問題，我們要介紹一個演算法，稱為「dijkstra」演算法
以下是dijkstra演算法的步驟
1. 至起始點找尋尚未拜訪的相鄰結點
2. 更新最短路徑表
3. 找尋目前未拜訪的最短路徑結點，將此結點設為起始點，並設為已拜訪
4.重複第一步，直到所有結點皆為已拜訪
此處拜訪的定義為---已得到最短路徑
以上面的例子做說明 ( - 代表無限大 ; D[i]: 1至 i的距離 ; P[i]: 至 i的上一個結點）
#1
起始點：1 （1已拜訪）
最短路徑表
D[1] D[2] D[3] D[4] D[5] D[6] D[7]
0 4 6 6 - - -
P[1] P[2] P[3] P[4] P[5] P[6] P[7]
1 1 1 1 1 1 1
#2
起始點：2 （1 2已拜訪）
D[1] D[2] D[3] D[4] D[5] D[6] D[7]
0 4 5 6 11 - -
P[1] P[2] P[3] P[4] P[5] P[6] P[7]
1 1 2 1 2 1 1
#3
起始點：3 （1 2 3已拜訪）
D[1] D[2] D[3] D[4] D[5] D[6] D[7]
0 4 5 6 11 9 -
P[1] P[2] P[3] P[4] P[5] P[6] P[7]
1 1 2 1 2 3 1
#4
起始點：4 （1 2 3 4已拜訪）
D[1] D[2] D[3] D[4] D[5] D[6] D[7]
0 4 5 6 11 9 -
P[1] P[2] P[3] P[4] P[5] P[6] P[7]
1 1 2 1 2 3 1
#5
起始點：6 （1 2 3 4 6已拜訪）
D[1] D[2] D[3] D[4] D[5] D[6] D[7]
0 4 5 6 10 9 17
P[1] P[2] P[3] P[4] P[5] P[6] P[7]
1 1 2 1 6 3 6
#6
起始點：5 （1 2 3 4 5 6已拜訪）
D[1] D[2] D[3] D[4] D[5] D[6] D[7]
0 4 5 6 10 9 16
P[1] P[2] P[3] P[4] P[5] P[6] P[7]
1 1 2 1 6 3 5
#7
起始點：7 （1 2 3 4 5 6 7已拜訪）
D[1] D[2] D[3] D[4] D[5] D[6] D[7]
0 4 5 6 10 9 16
P[1] P[2] P[3] P[4] P[5] P[6] P[7]
1 1 2 1 6 3 5
所以終端機1~終端機7的最短路徑花費為16
路徑為 1 → 2 → 3 → 6 → 5 → 7 (back trace)
程式碼；
https://github.com/xavierntnu/Data-Structure/tree/master/dijkstra
留言列表
進階程式設計 (C++) (2)