---
title: Greedy Algorithm / Shortest Path
tags: 演算法(交大OCW)
---
# Shortest Path

Shortest Path 有非常多的解法，這裡介紹的是第一個最簡單的版本

*Edsger W. Dijkstra 1959*

:::success
老師說他覺得他比較像是數學家
他的板書跟筆記非常棒，研究也大多在紙上，每一頁還會編號
:::

其實 Dijkstra 的這個解法同時解了另一個問題 Spanning Tree ，下一個章節會討論

*Robert C. Prim 1957*

但是因為有另一位 Prim 學者同時間也提出了解法(本質上跟 Dijkstra 是一樣的)
因此兩個問題的解法，前者以 Dijkstra 命名，後者就以 Prim 命名
:::info
圖靈獎得主獲獎時都要演說，講稿跟影片都找的到，可以去看

Dijkstra 在得獎時 (1972) 說過
*很多人寫了程式後就會遇到很長的 Debug 環節，浪費掉了很多時間
那應該做的就是不要讓 Bug 產生，也就是在設計時，就要確保邏輯是正確的*
:::

# 應用

## Google map

除了最短路徑，還有其他變形，像是最少油耗、最短時間(可能會塞車)等等

## Shopping Mall 的路徑機器
台灣比較沒有(2015)，但是外國的大型購物商城，要走到另一點會有點困難，於是就有這種機器幫你找出路徑

# 介紹

## 輸入

### 一個有方向性的 G(V,E)
當然也可以延伸出無方向性的版本

每個 E 上多了權重，在這裡代表距離
**注意，權重要大於等於 0**
>所以變形就是權重的部分，可以改成時間、花費等等

每個 V 就是你的地點
:::danger
權重要大於等於 0
因為很重要，所以要再多說一次
:::

### 一個起點 Source (s)

所以這個問題又叫做
**Single Source Shortest Path (SSSP)**

## 輸出

目標是給出，到達其他所有 V 的最短距離

原本只是想要得到兩點間最短距離，但是後來 Dijkstra 發現
他的解法可以得到全部點的最短距離，跟鬼一樣

---

# Dijkstra Algorithm

## Pseudo Code

// S：the set of explored nodes
// for each u in S, we store a shortest path distance d(u) from s to u
Dijkstra(G,L)
1. init S = {s}, d(s)=0
2. while S ≠ V do
3.    select a node v not in S with at least one edge from S for which

$$
4.\ d'(v)=min_{\theta=(u,v):u\in S}\{d(u)+L_{\theta}\}
$$

5.   add v to S and define d(v)=d'(v)

- S 是用來存放，已經算好最短距離的點

- d 這個變數是用來存放起點到達該點的最短距離
每個點都會有一個

- L 是某個 E 的長度函數，這裡的 E 是指 (u,v)
- 其中 u 是 S 內的某一點 ， v 是我要到達的點
也就是說，第四行目的是要找出
u 該點的最小距離，加上 (u,v) 這條 E 的距離的最小值

找到後就把 v 塞入 S ，並記錄他的 d value

## LINE 4 在做的事情


先列出 S 包含的點，也就是 s, u, v；以及以外的其他點，y, x, z

然後算出到達 y, x, z 的最短距離；不過由於已經知道到達 s, u, v 這三點的最短距離
所以我只要從這三點去看，有誰到達 y, x, z ，然後比較總距離的大小
例如要到達 x 的話，可以從 s, u, v，但是從 u 走的總距離是最短的，也就是 2
y 跟 z 兩點也一樣，可以分別得到 4 跟 5
從這三個數字中挑最小的，也就是到 x 的距離；把它存進 S


然後再做一樣的事情，從 s, u, v, x 這四點去看，到達 y, z 這兩點的最短距離
分別是 (x,y) 跟 (x,z)，但是 (x,y)=3 比較小，所以先把 y 加進 S
最後就是加入 z

## Greedy 的部分

這個方法就是每次只走距離最短的點，也就是由近到遠推進
因此 S 存的點的 d 值會越來越大

# 正確性證明 Stays ahead

## Loop invariant property

由於 Greedy 的主結構就是跑一個迴圈，通常是藉由說明這個 Loop 具備一個不變的 property，這個「不變的特性」可以使我們得出一個結果，來證明 Greedy 是正確的

以上面的SSSP來說，「不變的特性」就是那個集合 S 的部分，因為 S 裡面存放的是已經找到最短距離的點
我們只要證明，點被放進去後，最短距離就再也不會被改變，那當我結束迴圈，也就是找完所有點後，裡面存放的就是所有點的最短距離

而證明方法就是使用數學歸納法 Induction

## induction on |S|

這裡歸納法要歸納的是 S 的長度，也就是其所包含的點的數量

會使用 S 的點的數量是因為，我可以放進 S 裡面，代表那個點是「對的」，是已經找到最小值的

Basic step：當我執行第 1 個迴圈，|S| = 1
>因為一開始就只有起點 source 一定可以放進去，一定是對的

Induction step：假設執行第 k 個迴圈，k ≧ 1，|S| = k 是正確的
也就是說 S 裡面存有了 k 個找到最小值的點

此時執行第 k + 1 個迴圈


1. 上圖中，假設 v 是經過計算後，距離最短的點，為了方便說明，把跟他有 E 且在 S 內的點叫做 u

2. 假設有另一條 path 不是經由 u ，而是 S 內別的點到達 v，我們叫這連接 S 內部跟外部的兩點 x 跟 y；也就是說，我可以從 s 經由 x 到達 v，而 x 來開 S 後第一個連接的點叫 y

3. 由於程式碼在第 k + 1 次時選擇了 v ；也就是說，s 經過 x 到 y 的距離大於或等於 s 經過 u 到 v 的距離

5. 而從 S 內部， u 以外的其他點到達 v ，距離一定會比較長，因為多了 P 這條路
或是一樣長，也就是說 P 的長度是 0

6. 也就是說，s 經由u 到 v 一定是最小值，放進去以後就絕對不會再變動了

:::info
這裡也就是為何一開始的條件中，每條路的長度，也就是權重一定得要大於等於 0
如果可以為負數的話，上面第 4 點的推論就會出錯

而負數的權重，則要使用別的演算法，像是使用 Dynamic programming 的其他演算法
:::

---

# 實作的要點

## 構想

S 以及 Line 3、4，需要搭配特殊的結構，避免讓「尋找最短距離的點」這個步驟變得複雜

想法跟上面的程式碼有些不同，上面是從 Edge 的角度出發，也就是對於每個 S 內的點，都去檢測跟他相連的且不在 S 內的點

但是這會讓複雜度飆升，所以就轉成從點的角度出發；因為每個點都持有一個 d value，那我每次就吐出一個 d value 最小的點進行分析

## 實作

一開始 source 初始化，會把 d 值設為 0，而其他每個點都定為無限大

建立一個 min priority queue，裡面塞入每個點；每次執行迴圈時，吐出 d value 是最小的點
>因此， source 會是第一個被這個 queue 吐出來分析的點

將這個點塞入 S 裡面，表示他已經到達最小距離，並同時更新與他相連的點的最短距離；如果更新後的最短距離比原本持有的最短距離還要小，那就更新成新的最短距離

之後再一次從 queue 吐出 d value 最小的點 ，重複下去


:::info
至於要如何實作這個 min priority queue，底下會說明
:::

## 時間複雜度

下面這張圖，Dijkstra 代表的是上面最一開始的構想所花費的時間
而左側的欄位代表演算法需要的操作


1. Insert
- 一開始把每個人丟進 min priority queue
3. Extractmin
- 把 d 最小值給抽出來
5. ChangeKey
- 更新鄰居的 d value
7. IsEmpty
- 檢查 queue 是否空了
:::success
上面的圖給出了四種實作 min priority queue 的方法
這堂課主要介紹使用 Binary heap，而且 heap 還可以拿來快速排序，好耶
:::

在更新 d value 的部分，相較於最一開始的構想 (Dijkstra)，也就是對 S 內每個點，都去更新他們的鄰居並找最小值；
上面藉由 queue 吐出一個點，並只更新他的鄰居的這個做法，可以降低所需時間，因為後者只要執行 「 Edge 數量的次數」 就好

### Fibonacci heap

老師說這是一個研究很仔細後的結果，但是要注意一點是，他的係數很大
也就是說，在處理資料量較小的時候，用 Binary heap 就好

---

# Priority Queue

有兩種，一個是 index 最大優先，另一個是最小優先；但其實兩者是一樣的，只是順序顛倒而已

:::info
- 最大的就叫做 Max Priority Queue；最小的就是 Min Priority Queue

- 當資料伴隨著一個 key 的時候，通常就會採用 Priority Queue
:::

一個 Priority Queue 會有下面四種操作


- FindExtreme
- 圖片寫Min是因為他例子用 Min Priority Queue
- 這個功能就是找出極值
- ExtractExtreme
- 這個功能就是吐出極值，把他從 Queue 移除的意思
- Insert
- 就是插入一筆資料，記得，要根據 Key 插入
- ChangeKey
- 改變 Key 的大小，也就是改變重要性

而實作 Priority Queue 的方法，就是使用 Heap

這裡為了講排序，所以採用 Max Priority Queue

# Heap

## 定義

1. A max/min heap：key[parent]≧/≦key[children]
2. A Complete Binary tree

所謂「完整」，如下圖，所有成員會依照編號排好；記住，由於他是二元樹，所以只有 Leaves 可能會殘缺，但是以上的部分一定是完好的
且殘缺一定是在右下角


:::info
所以可以知道，該 Heap 所代表的極值一定在 root，另一個極值會在 Leaves 的某處
:::
:::warning
要注意，Binary Heap 只確保父子間的大小關係，並沒有確保手足間的大小關係
因此，兄弟的孩子跟自己的關係也是沒有保證的，像是叔叔的值比姪子大之類的事不一定會發生

像上圖 Max heap 的第 3 個元素 7 ，他比他兄弟的孩子(也就是 12 底下的 10 跟 8)的值來的還要小
:::
## 實作 - Array

是的，Heap 是用 Array 實作。下面為了方便，不用第 0 格

這樣一來，父元素跟第一個子元素的 index 關係就是 2 倍
像底下 14 的 index 是 1 ， 12 的 index 是 2
12 的 index 是 2，10 的 index 是 4


然後一個 heap 還會記錄

1. Heapsize
- 紀錄這個 Heap 目前的數量
<!-- - 但可能會算在 Array 裡面 -->
3. Capacity
- 也就是 Heap 所在的 Array 最大的容量

## Push Θ(logn)

以上面的例子。無論如何，先把他塞到最後面
:::info
其實這個例子已經先塞入" 1 "了
:::
>塞入 21


這時候要做的事情就是，**跟他的爸爸比較**
根據這個 Heap 的種類，看是比較大就往上移，還是比較小就往上移
由於兄弟間沒有大小關係，所以就單單只要父子比較就好

因此，時間複雜度就是 Θ(logn)(上下界都是)

## Pop Θ(logn)

因為 Heap 的作用就是決定 Priority，因此要吐也是要吐出 Priority 最高的，也就是 Root

但是吐完後，要維持住大小關係。
1. 先把最後一個元素，給移到 Root O(1)
2. 之後開始糾正大小關係 Θ(logn)
1. 首先讓 Root 的兩個子元素比較大小
2. 比較出來後再跟 Root 交換
3. 持續執行值到正確的大小關係


---

# Max / Min Heapify O(nlogn)

也就是讓一堆沒有序列的數字，符合 Heap 的形式。最一開始的構想跟數學歸納法很像。

而我們有個循環的步驟：

1. 我每次就挑選一個子元素，然後去跟他的父元素比較大小關係
2. 假設子元素底下已經構成一個 Heap，那當我比較完大小關係後，就可以讓父元素準確的沉下去

那起始的步驟，也就是歸納法的第一步要怎麼挑呢？就是從 Leaves 開始
因為 Leaves 底下沒有任何元素，所以他自己就是一個 Heap


上圖就是從 Leaves 開始，找其對應的 父元素 去比大小
而且由於 index 從 1 開始，所以我偶數位，也就是 2n，跟 2n + 1 的就會是兄弟
兄弟間比完大小，再用 2n/2 找到父元素，去跟比完大小的兄弟比大小，十分方便

由於會遍歷整個元素，且對每個元素都要移動父元素，所以會是 O(nlogn)

:::info
其實跟上面的 Push 後要維持大小關係的方法很類似，不過由於無法確保其他部分的大小關係，所以只能從底部往上做
:::

## Heap Sort

將 Heapify 好的 Heap 的 Root 的值跟最後一個元素交換，並改變 Heapsize，因此移動到底部的極值並不會被影響。
然後重整一次大小關係。

由於是已經 Heapify 過的，所以跟 Pop 一樣，每次只要 logn 的時間就可以調整好大小關係；共有 n 次，因此總共的時間複雜度就是 nlogn

而且因為從頭到尾都是對同一個陣列進行操作，所以空間使用非常有效率，很省空間

而且因為是當下馬上做，所以是 Impress sorter(？

:::info
當然還有其他的方法時間複雜度一樣
merge sort
:::