※推薦評價好的iphone維修中心
擁有專業的維修技術團隊，同時聘請資深iphone手機維修專家，現場說明手機問題，快速修理，沒修好不收錢
Dijkstra也叫迪傑斯特拉，是典型最短路徑算法，計算一個起始節點到路徑中其他所有節點的最短路徑的算法和思想。在一些專業課程中如數據結構，圖論，運籌學等都有介紹。其思想是一種基礎的求最短路徑的算法，通過基礎思想的變化可以解決很多複雜問題，如導航線路，動態規劃等。
Dijkstra 算法思想介紹
如下圖是一個多節點，多路徑圖。下面以該圖為例子講解dijkstra算法尋找最短路徑的過程。
以A點為起始點，求A點到其他點 B C D E F 5個點的最短路徑，最後得出A到其他點的最短路徑。
因為要求A到其他5個點的最短距離，所以構造一個數組記錄A到B C D E F 5個點的路徑距離。約定：
- 如果A能夠直接達到節點，則使用路徑長度即權值作為其距離
- 如果A節點不能直接達到節點則使用無窮大表示A到該點距離。
- 任何點到自身都為0
那麼在最開始時，A點到圖中所有點的距離數組如下：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 10 | 無窮大 | 4 | 無窮大 | 無窮大 |
dijkstra的算法思想是從以上最短距離數組中每次選擇一個最近的點，將其作為下一個點，然後重新計算從起始點經過該點到其他所有點的距離，更新最短距離數據。已經選取過的點就是確定了最短路徑的點，不再參与下一次計算。
可能看到這裏你完全不明白dijkstra算法的思想，心裏可能想：這是說的人話嗎？不要緊，如果算法一句話就能解釋清楚，那就不會出現那麼多算法書了。下面我們就從實際的選取過程中理解這個思想的精髓。
第一次選取
構建好的數組是這樣的：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 10 | 無窮大 | 4 | 無窮大 | 無窮大 |
第一步選取該最短路徑數組中值最小的一個點。因為A點到本身不需要參与運算，所以從剩下的點中選擇最短的一個是D。
第二步以A-D的距離為最近距離更新A點到所有點的距離。即相當於A點經過D點，計算A到其他點的距離。
A-A : 0
A-B : A-D-B:6
A-C : A-D-C:19
A-D : A-D:4
A-E : A-D-E:10
A-F : A-D-F:去窮大
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 19 | 4 | 10 | 無窮大 |
將現在A到各個點的距離和之前的比較，到相同點取最小值。更新了B C E的距離，得到如下新的最短距離數組：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 19 | 4 | 10 | 無窮大 |
同時現在A D兩點已經計算過，不參与下面的計算。
第二次選取
第二次選取的數組為第一次中更新過最短距離的數組
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 19 | 4 | 10 | 無窮大 |
第一步：因為A D 不參与選取，所有從剩下的點中選取最近距離是點B
第二步：以B為最新點，更新最短數組
A-A : 0
A-B : A-D-B:6
A-C : A-D-B-C:14
A-D : A-D:4
A-E : A-D-B-E:12
A-F : A-D-B-F:無窮大
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 14 | 4 | 12 | 無窮大 |
對比現在的最短距離和上一個數組的距離，到相同節點取最小的，C點由19更新成14，E點走A-D-E為10，距離更短所以不更新（敲黑板，這個重要），得到如下數組：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 14 | 4 | 10 | 無窮大 |
此時B點加入最短路徑範圍中。
第三次選取
上一步得到的數組為：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 14 | 4 | 10 | 無窮大 |
第一步：選取除了A B D節點之外的剩餘節點中最短節點，為點E
第二步：以E點為最新節點，更新最短路徑數組
因為在上一部中計算達到E點的距離時沒有更新距離，A-D-E 為10 最短，所以更新E點到B C F點的距離時走的路徑是A-D-E。注意這裏的最短距離有對應的路徑，選擇最小值就是選擇最短距離。
A-A : 0
A-B : A-D-B:6
A-C : A-D-E-C:11
A-D : A-D:4
A-E : A-D-E:10
A-F : A-D-E-F:22
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 11 | 4 | 10 | 22 |
對比現在的最短距離和上一個數組的距離，到相同節點取最小的，更新C點走A-D-E-C 為11，比之前的A-D-B-C14距離更近，更新到F點距離，得到如下數組：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 11 | 4 | 10 | 22 |
此時E點加入最短路徑範圍中。
※網頁設計最專業,超強功能平台可客製化
窩窩以「數位行銷」「品牌經營」「網站與應用程式」「印刷品設計」等四大主軸，為每一位客戶客製建立行銷脈絡及洞燭市場先機。
第四次選取
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 11 | 4 | 10 | 22 |
第一步：選取除了A B D E節點之外的剩餘節點中最短節點，為點C
第二步：以C點為最新節點，更新最短路徑數組
A-A : 0
A-B : A-D-B:6
A-C : A-D-E-C:11
A-D : 4
A-E : A-D-E:10
A-F : A-D-E-C-F:16
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 11 | 4 | 10 | 16 |
對比現在的最短距離和上一個數組的距離，到相同節點取最小的，更新到F點距離，可以得到如下數組：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 11 | 4 | 10 | 16 |
第五次選取
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 11 | 4 | 10 | 16 |
第一步：選取除了A B C D E節點之外的剩餘節點中最短節點，也就是最後一個節點：F
第二步：以F點為最新節點，更新最短路徑數組。由於F點是最後一個點，所以也不用更新數組，目前的數組就是所求數組
將F點加入最短路徑範圍中，此時所有的點都加入了最短路徑範圍，也就是說A點到所有點的距離都找到了。最總得出的距離值為：
最終得到的結果為：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 11 | 4 | 10 | 16 |
最終結果
相應的A點到所有點的最短路徑走法最終得到的結果為：
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 6 | 11 | 4 | 10 | 16 |
A-A:0
A-B : A-D-B:6
A-C : A-D-E-C:11
A-D:4
A-E:A-D-E:10
A-F:A-D-E-C-F:16
算法總結
Dijkstra算法作為求最短路徑的經典算法，個人理解為算法提供了一種思想，每走一步都是找到最短的路徑，並且每走一步都實時更新所有距離，保證每次都選擇最短路徑。
python實現Dijkstra
將以上的過程使用python來實現。
首先總結一個Dijkstra算法的核心思想，分成兩步走：
- 構造一個最短路徑數組，每次找到數組中未訪問的節點里最小的點
- 以上一步的節點為最新節點，更新起始點到所有點的距離
使用python就是實現這兩步即可
數據準備
二維矩陣
如何描述一個圖呢？通常有兩種方式，分別是：十字鏈表和二維矩陣。因為二維矩陣更加直觀，所以選擇二維矩陣。
將上面的圖描述成一個二維矩陣
無窮大使用MAX = float('inf')表示，該數值是python中表示無窮大的一個值。
這個二維矩陣真正直觀之處在哪裡呢？是能夠看到任意一個點到其他點的距離。如想看D點到其他點的距離，就是：
在我們的算法兩步走中第二步要更新A點經過某點到其他點的距離，正是使用了這個特徵。
MAX= float('inf')
matrix = [
[0,10,MAX,4,MAX,MAX],
[10,0,8,2,6,MAX],
[MAX,8,10,15,1,5],
[4,2,15,0,6,MAX],
[MAX,6,1,6,0,12],
[MAX,MAX,5,MAX,12,0]
]
最短路徑數組
在上面講解算法過程中有一個重要的的最短路徑數組，不斷更新該數組直到所有的點都被訪問到。使用python語言，構造該數組：
distance = [MAX] * len(matrix)
len(matrix) 實際上算出的圖的點的個數。初始化時所有的節點都是不可達。
在算法過程中還有一個重要的數組，並沒有體現出來，但是在python計算時也很重要，那就是訪問過的點。每一次訪問之後就要將訪問過的點加入到該數組中，這樣做是為了避免重複訪問。
used_node = [False] * len(matrix)
初始化時認為所有點都沒有訪問到
代碼實現
MAX= float('inf')
matrix = [
[0,10,MAX,4,MAX,MAX],
[10,0,8,2,6,MAX],
[MAX,8,10,15,1,5],
[4,2,15,0,6,MAX],
[MAX,6,1,6,0,12],
[MAX,MAX,5,MAX,12,0]
]
def dijkstra(matrix, start_node):
#矩陣一維數組的長度，即節點的個數
matrix_length = len(matrix)
#訪問過的節點數組
used_node = [False] * matrix_length
#最短路徑距離數組
distance = [MAX] * matrix_length
#初始化，將起始節點的最短路徑修改成0
distance[start_node] = 0
#將訪問節點中未訪問的個數作為循環值，其實也可以用個點長度代替。
while used_node.count(False):
min_value = float('inf')
min_value_index = 999
#在最短路徑節點中找到最小值，已經訪問過的不在參与循環。
#得到最小值下標，每循環一次肯定有一個最小值
for index in range(matrix_length):
if not used_node[index] and distance[index] < min_value:
min_value = distance[index]
min_value_index = index
#將訪問節點數組對應的值修改成True，標誌其已經訪問過了
used_node[min_value_index] = True
#更新distance數組。
#以B點為例：distance[x] 起始點達到B點的距離，
#distance[min_value_index] + matrix[min_value_index][index] 是起始點經過某點達到B點的距離，比較兩個值，取較小的那個。
for index in range(matrix_length):
distance[index] = min(distance[index], distance[min_value_index] + matrix[min_value_index][index])
return distance
start_node = int(input('請輸入起始節點:'))
result = dijkstra(matrix,start_node)
print('起始節點到其他點距離：%s' % result)
結果：
請輸入起始節點:0
起始節點到其他點距離：[0, 6, 11, 4, 10, 16]
簡單總結
學習python實現Dijkstra重要的地方有幾點：
- 數據構造 二維矩陣表示圖
- 圖的訪問方式 更新最短路徑數組的過程無非就是分別比較二維矩陣數組中某一行的值和最短路徑數組的值
熟悉這樣的處理方式，再有類似的算法也能找到解決的思路。例如一個二維矩陣，從起始點開始只能走向下的相鄰的元素，求達到某點的最短路徑。
希望通過該篇文章，能夠深刻理解Dijkstra算法，做到心中有數，手中有活。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
※台北網頁設計公司這麼多該如何選擇?
網動是一群專業、熱情、向前行的工作團隊,我們擁有靈活的組織與溝通的能力,能傾聽客戶聲音,激發創意的火花,呈現完美的作品