本文同步於個人Blog → InformisTry - HankLee

前言

今天是這一個系列文章所要正式介紹的最後一個演算法了，而今天要講的這個演算法也是屬於Greedy Algorithm的其中一員，就是Dijkstra's Algorithm。

Dijkstra's Algorithm是什麼

Dijkstra's Algorithm基本上是用來解決最短路徑的問題，因此在進行之前，一樣會將資料設定成Graph的資料型態，然後一樣紀錄了每個點與點之間的關係與距離，然後再一步步的推敲與計算；在Dijkstra's Algorithm的概念中，由於都不知道要去每個點的距離是多少，因此每個點的距離值都會設定為無限大，然後再一步步的計算。

Dijkstra's Algorithm的流程

Dijkstra's Algorithm基本上的流程如下：

1. 先將每個點的距離設定成無限大。
2. 選擇一個起始點，並將這個起始點的距離值設定為0（因為從它開始，故自己到自己的距離為0）
3. 再從這個節點計算去『鄰居』的距離
4. 選擇最短距離的鄰居為下一個節點，並紀錄下距離。
5. 反覆進行3, 4步驟，直到所有節點都經過一輪。

從上GIF中可以看到，計算距離時，會將其數值疊加，這樣才能算出點與點之間的最短距離，一但計算的距離比舊的距離還小，就會取代原先的數值，然後再從中選出距離最短的繼續進行，直到所有的點都有其數據。

小結

Dijkstra's Algorithm進行前，會先預設抵達所有節點的距離為無限大，再從中選一個起始點開始計算，一步步地改變每個節點的距離，最後才取得抵達每個節點的最短距離。

預告

最後三天，我們會來破解一個腦力遊戲，明天再來揭曉。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin