Dijkstra演算法解決最短路徑問題

Dijkstra演算法是大學計算機專業要學習的一種演算法，剛剛接觸的時候會感覺非常的不好理解，今天就用一個例子來教給大家怎麼一步一步的去理解這個演算法。

操作方法

（01）例子直接看圖吧，我們這是一個無向圖，首先我們需要找到一個起點，為了方便我們直接按照字母的順序來，從a點開始

（02）然後我們找出其餘所有的與a點相連的點，並根據路徑上的權值計算出長度如圖中的一樣先寫上

（03）然後我們來確定第二個點，根據上一步的結果我們可以發現到b的權重是最小的，所以我們確定第二個點是b點，a--b 此時b的權重為3

（04）然後我們找第三個點，現在已經是走到b點了，所以接下來的一步是從b點開始向外延伸，再找出所有與b相連的點，再根據路徑上的權值和b點的權值計算出所有與b點相連的點的權值。

（05）根據上一步的結果我們可以確定d點是權值最小的點，所以第三個點應該是d點。

（06）以此類推，下面的幾個點依然是用這種方式來確定，與d點相連的有c e兩個點，我們計算出來長度是c（d,10）e(e,9)

（07）此時c的權重為10，而上一步c的權重為7，所以應該選擇邊b--c 而不是d---c

（08）最後一個點e,根據上面的點和路徑上的值，來算出權值，根據結果要選擇路徑d--e

（09）根據上面的每一步的結果最後連起來就是這個圖的最短路徑。

特別提示

本人能力有限，表達不清楚的地方歡迎詢問指正

發現錯誤可以給我私信留言