代克思托演算法 (Dijkstra's algorithm)


Dijkstra's algorithm 是以某一節點為出發點,計算從該節點出發到所有其他節點 的最短路徑。

首先以某一節點當作出發點,在與其相連且尚未被選取的節點裡,選擇加入離出發點距離 最短的節點,並且透過新增的節點更新到達其他節點的距離。 如此重覆加入新節點,直到所有的節點都被加入為止。

※ 請把課本 P.317頁,圖11-20 e 到 c 邊的權重,從8 更正為 6。

  1. 起始。


    步驟即將新增
    abcdefg
    1-------a
    ps. "-" 代表目前無法到達,所以距離為無限大,即課本的

  2. 從 a 開始,與 a 相連的節點有兩個 (f, b)。
    a 與 a 的距離為 0。 (新增 0)
    f 與 a 的距離為 3。 (新增 3)
    b 與 a 的距離為 32。 (新增 32)


    與 a 距離最短的節點為 f。
    步驟即將新增
    abcdefg
    1-------a
    2032---3-f
    ps. 加入後的節點將著色顯示。

  3. 加入 f 後,與 f 相連的節點有兩個 (c, b)。
    透過 f , c 與 a 的距離為 3 + 2 = 5。 (新增 5)
    透過 f , b 與 a 的距離為 3 + 7 = 10。 (取代 32)


    與 a 距離最短的節點為 c。
    步驟即將新增
    abcdefg
    1-------a
    2032---3-f
    30105--3-c

  4. 加入 c 後,與 c 相連的節點有三個 (b, e, g)。
    透過 c , b 與 a 的距離為 5 + 21 = 26。 (保留 10)
    透過 c , e 與 a 的距離為 5 + 6 = 11。 (新增 11)
    透過 c , g 與 a 的距離為 5 + 11 = 16。 (新增 16)


    與 a 距離最短的節點為 b。
    步驟即將新增
    abcdefg
    1-------a
    2032---3-f
    30105--3-c
    40105-11316b

  5. 加入 b 後,與 b 相連的節點有一個 (e)。
    透過 b , e 與 a 的距離為 10 + 12 = 22。 (保留 11)


    與 a 距離最短的節點為 e。
    步驟即將新增
    abcdefg
    1-------a
    2032---3-f
    30105--3-c
    40105-11316b
    50105-11316e

  6. 加入 e 後,與 e 相連的節點有一個 (d)。
    透過 e , d 與 a 的距離為 11 + 13 = 24。 (新增 24)


    與 a 距離最短的節點為 g。
    步驟即將新增
    abcdefg
    1-------a
    2032---3-f
    30105--3-c
    40105-11316b
    50105-11316e
    601052411316g

  7. 加入 g 後,與 g 相連的節點有一個 (d)。
    透過 g , d 與 a 的距離為 16 + 9 = 25。 (保留 24)


    與 a 距離最短的節點為 d。
    步驟即將新增
    abcdefg
    1-------a
    2032---3-f
    30105--3-c
    40105-11316b
    50105-11316e
    601052411316g
    701052411316d

  8. 加入 d 後,所有結點皆已加入,所以Dijkstra's algorithm完成。


    所有節點與 a 的最短距離如下:
    abcdefg
    a01052411316