基礎演算法系列 — Graph 資料結構與Dijkstra’s Algorithm
Graph，在資料結構中也是一個基礎且非常重要的一個資料結構，用於表示物體與物體之間存在某種關係的結構。定義中，會由點(物體)與線(物體間的關係)，來描繪出一個 Graph，如下圖就是一個簡單的 Graph：
有向圖與無向圖
如果兩點間的線(關係)，有著方向性的關係，我們會使用箭頭來表示方向性。而一個圖中的線如果都是有方向的，稱之為「有向圖」，反之如一開始的範例就是「無向圖」，同時具備兩種的圖則稱為「混合圖」。
如何表示一張圖？
由於一個圖中的節點，可能同時與多個其他節點相連，常見的表示方法會使用矩陣或是 linked-list 來表示。
- Adjacency Matrix(相鄰矩陣): 使用二維陣列，有關聯的點之間為 1
- Adjacency List(相鄰串列): 使用 Linked-List，鏈結的點順序不重要
Adjacency Matrix(相鄰矩陣)
Adjacency List(相鄰串列)
Shortest Path Problem
最短路徑問題是圖論研究中的一個經典演算法問題，核心目的在尋找圖中兩結點之間的最短路徑，現存也很許多針對不同情境、不同的演算法可以解決這個經典問題。
Dijkstra’s algorithm
Dijkstra’s Algorithm 可以說是很常聽到、關於找最短路徑的演算法，他的概念是一種 Greedy 演算法，每次都去找當前最小的那一條路。這裏直接拿剛剛的圖，在每個邊上給予權重，然後找尋 A → E 的最短路徑。
延伸閱讀：演算法筆記系列 — Greedy Algorithm 貪婪演算法
首先在一開始的時候，我們先建立一張表，用來記錄三件事：
- Visited: 有沒有走過這個點，預設為 False
- Cost: 從起點到這個點所需路程，預設為無限大
- Path: 這個點的上一個相連點，預設 -1 (或是任何可以代表非圖上點的值)
演算法：
- 每次更新移動點可以到達相鄰點的路程 (Cost) 與前一個點 (Path)
- 從所有未訪問過 (Visited) 的點中，找出路程最短的點當作下一個移動點
條件：
- Graph 不可以有負數的權重
一開始移動點為 A，此時更新所有 A 可以碰到的相鄰點 B & C，更新他們的 Cost & Path。接著從所有尚未訪問過的點 B~E 之中，選出路徑最短的 C 作為下一個移動點。
在移動點為 C 的時候，這時候更新他可以到達的點 E，Cost 等於 Cost [C] + Cost [C-E] = 2 + 10 = 12，並且挑選再下一回合的移動點。
接著進行下一回合的移動點挑選，從還未走過的 B、D、E 當中，挑出距離最近的 B ，作為下一回合的移動點。
接下來的移動點 B，會去更新他相鄰還沒走過的點 D、E，這時候由於 E 已經有值了，所以要比最新的值與本來的值，找出最小的距離。我們可以找到從 B 點到 E 點會比本來的 C 點到 E 點距離還要進，所以更新 E 的 Cost 並且把前一個點也更新為 B。
重複一樣的動作，直到我們目標要找的點 Visisted = true
最後就可以找出我們的最短路徑為：
A → B → D → E，總共需經過的 Cost = 8
如果你覺得這篇文章對你有幫助，歡迎買杯咖啡贊助 ☕️ 謝謝
