# Data Structure - Graph : 最短路徑
###### tags: `Data Structure - Graph`

### (一) . 基本概念
1. $Shorted \ Path$ : 一個權重圖兩點的權重加總最小的 $path$。
2. $Source$ : 一個 $path$ 的起點。
3. $Destination$ : 一個 $path$ 的終點。
4. $Single\ source \ All \ destinations$ :一種最小路徑的問題概念。
- $Single\ source$ : 單一起點。
- $All \ destinations$ : 到所有點為終點的問題。
- 此問題為由一點到同一個圖中，所有點的最短路徑。

### (二) . Dijkastra Algorithm (類DFS的演算)
1. 前提準備 ：
- 一個 $S$ 集合 ： 點集合，一開始只有一個起點。
- 一個 $V$ 集合 ： 點集合，為還沒經過的點。
- 一個 $Table$ : 存放其他每一點的最短路徑和前繼者。
- $Path$ : 將最短路徑的值都先設為無限大。
- $Pre$ : 前繼者為由哪點到此點。
2. 演算法 ： $N$為當前指向的節點，$k_0 - k_i$為N相鄰的節點。
- 終止條件 ： $V=∅$ 時。
- 迴圈行為 ： 對$N$的第$i$個相鄰的點$Path$改為$min(Path(k_i),Path(n)+edge(N→k_i))$
- 迴圈行為 ： 若$Path$改變則將第$k_i$的$Pre$設為$N$。
- 迴圈行為 ： $N$改變為相鄰中最小權重的節點，並將其從$V$中移除。

3. 時間複雜度 ： 對一個$G(V,E)$的圖，複雜度會因為圖的儲存方式的不一樣而變。
- $adjacent\ list$ : $O(|V|^2)$。(因為每一點都要遍例，每一個又要遍例相接的)。
4. 補充 ：
- 此方法也可以用於找最長路徑。將path初始化為0，max取代min即可。
- 可以用於求所有的最短路徑，對每個點都做一次就好了。

### (三) Transitive closure
1. $Transitive\ closure\ matrix$ : 對一個圖$G(V,E)$。
- 若點 $i$ 和 $j$ 有一條 $path$的 $length > 0$ 。
- 則$A[i][j]=1$。反之則為$0$。
2. $Reflect\ Transitive\ closure\ matrix$ : 對一個圖$G(V,E)$。
- 若點 $i$ 和 $j$ 有一條 $path$的 $length ⩾ 0$ 。
- 則$A[i][j]=1$。反之則為$0$。