【舌尖上的演算法】Day27 -- Greedy Techniques - Dijkstra's Algorithm

2020 IT邦鐵人賽

Posted by Hank Lee on Sunday, October 4, 2020

2 Minutes Read

Table of Contents

本系列文章同步分享於IT邦幫忙第12屆鐵人賽

前言

今天是這一個系列文章所要正式介紹的最後一個演算法了,而今天要講的這個演算法也是屬於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步驟,直到所有節點都經過一輪。

Dijkstra’s Algorithm

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


小結

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


預告

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


References

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