Table of Contents
前言
今天是這一個系列文章所要正式介紹的最後一個演算法了，而今天要講的這個演算法也是屬於Greedy Algorithm的其中一員，就是Dijkstra’s Algorithm。
Dijkstra’s Algorithm是什麼
Dijkstra’s Algorithm基本上是用來解決最短路徑的問題，因此在進行之前，一樣會將資料設定成Graph的資料型態，然後一樣紀錄了每個點與點之間的關係與距離，然後再一步步的推敲與計算；在Dijkstra’s Algorithm的概念中，由於都不知道要去每個點的距離是多少，因此每個點的距離值都會設定為無限大，然後再一步步的計算。
Dijkstra’s Algorithm的流程
Dijkstra’s Algorithm基本上的流程如下：
- 先將每個點的距離設定成
無限大。 - 選擇一個起始點，並將這個起始點的距離值設定為0（因為從它開始，故自己到自己的距離為0）
- 再從這個節點計算去『鄰居』的距離
- 選擇最短距離的鄰居為下一個節點，並紀錄下距離。
- 反覆進行3, 4步驟，直到所有節點都經過一輪。
從上GIF中可以看到，計算距離時，會將其數值疊加，這樣才能算出點與點之間的最短距離，一但計算的距離比舊的距離還小，就會取代原先的數值，然後再從中選出距離最短的繼續進行，直到所有的點都有其數據。
小結
Dijkstra’s Algorithm進行前，會先預設抵達所有節點的距離為無限大，再從中選一個起始點開始計算，一步步地改變每個節點的距離，最後才取得抵達每個節點的最短距離。
預告
最後三天，我們會來破解一個腦力遊戲，明天再來揭曉。