今年是2021，資芽的二階主題跟2020上的有很多的差別，因此會利用暑假把2020的東西也補一補！
課程內容
路徑與權重
- $G=(V,E)$
- 尋找最短路徑權重和最小
- 無帶權：BFS直接做(or DFS)
- 有帶權最短路徑
Floyd-Warshall：全點對最短路徑(All Pairs)
不支援負環
想法：DP轉移（三個迴圈中點、起點、終點依序鬆弛）
- $d[i][j] = mid(d[i][j],d[i][k]+d[I][k]+d[k][j])$
- 如果改寫成定義 $dp[k][i][j]$ 為點 $i$ 走到點 $j$ ，只能經過前k個點的最短路
- 則轉移：$d[k+1][i][j] = min(d[k][i][j], d[k][i][k+1]+d[k][k+1][j])$
- 因此中間點k必須在最外層（不過有論文指出順序顛倒一樣可以得到正確解）
- 優點：實作容易，缺點：時間 $O(v^3)$ 、無法處理負環（可處理負邊）
Dijkstra’s：單點源最短路徑
優點：時間 $O(E+V^2)$、無法處理負邊
想法：Greedy（和DP）
- 維護：1. 未拜訪的節點集合$U$ 2. $d[i]$ 目前起點到 $i$ 最短路 3. 目前考慮節點 $p$
- 重複以下動作直到u為空：
- 對於所有與 $p$ 連接的節點 $q$，$d[q] = min(d[q],d[p]+weight[p][q])$
- 當 $p$ 相鄰節點都走過：在 $u$ 中移除 $p$
- 將 $p$ 更新成U中離起點距離最短的點 $min(d[j])$
- 可以變成 $O((E+V)logV)$->邊較為稀疏的圖時有利（使用priority_queue）
- 不能處理負邊，因為 $d[i]$ 較小的處理完之後就不會再更動了，加入負邊可能更小
- 拿距離最小的點 $k$ 去更新其他點，不能保證更新後其他點一定是最短路
- 上一步走完 $k$ 連接所有邊後，從集合 $U$ 中移除，因為沒有負邊， $k$ 必定是最短路
Bellman-Ford：單點源最短路徑
可以處理負環
時間：$O(VE)$
- 想法：Relax鬆弛
- 一條邊 $\delta(u,v)$ 滿足 $dis[v] = min(dis[v],dis[u]+weight[u][v])$
- 對每一條邊進行鬆弛，因為鬆弛沒有按照最短路順序，因此要做V-1次
- 此為暴力作法
- 執行V-1次的worst case：
- 剛好跟最短路徑的順序相反
- 每次 Relax 後只能優化單一子路徑
- 共有V個頂點，需要有V-1 條子路徑，每一次一條
- 檢查負環：做完之後卻有滿足$d[v] > d[u]+w(u,v)$ ，表示有負環
優化：SPFA(Shortest Path Faster Algorithm)
每次只relax更新過的點
使用queue優化，有點像BFS過程
- 1.把起點 Push 到 Queue
- 2.從 Queue 裡 Pop 出一筆資料
- 3.該筆資料的所有邊進行 Relax
- 4.有更新到的頂點再 Push 到 Queue
- 5.重複步驟 2 ~ 4，直到 Queue 為空
- 時間：$O(VE)$ ->worst case，期望 $O(KE)$ ，K大概是2吧（反正挺快的）
DAG Shortest Path
首先對所有點進行拓墣排序，花上時間 $O(V+E)$，接著對每一條邊進行鬆弛，時間$O(E)$，因此總時間複雜度是 $O(V+E)$。這個時間複雜度是很快的，但相對的限制也非常多，除了不能有負邊與負環之外，更不能有正環在其中，否則不能進行拓墣排序（在之前筆記進階圖論（一））有提到，也就是這一中圖必須是DAG(Directed Acyclic Graph)！
一個有趣的應用：PERT
最短路徑樹
紀錄predecessor(樹父節點唯一)
起點到每個點的最短路徑都唯一的話，那把這些路徑疊起來會變成一棵樹
- 樹：每一點都有唯一來源（最短路）
最短路徑比較
最短路徑問題共有以下求解方式（當然還有一堆），整理比較圖：
負環
上表中的可以處理負環的SPFA和Bellman-Ford是以什麼樣的方式處理？（遇到負環權重應該是$-\infty$）上方所謂負環是指下圖這種情況（當出發點為s，終點為t求最短路徑的問題），因為沒有經過負環，因此 $\delta(s,t)$ 可以被SPFA和Bellman-Ford求出正確的最短路徑為1。我們可以利用從終點回朔最短路徑（利用predecessor紀錄）看是否有重複經過的點，如果有則表示途中有經過負環！
至於其他的算法，都會求出不正確的數值！
Floyd warshall
這個演算法是處理全點對的最短路徑，如果有負環，那一定有任兩點的最短距離是錯誤的。不過我們一樣可以利用Floyd-Warshall演算法判斷圖中是否有負環，只要檢查每一個點走到自己的距離是否為負 ，即$dis[i][i]<0$ 是否成立，如果成立表示圖中有負環。
Dijkstra
這個演算法要求的限制更多，圖中不可以有負邊（更別提多個負邊組成的赴環），原因是在Dijkstra求最短路的過程中使用到貪心的想法，當我們從heap裡面取出目前距離最短的點之後，便不會再次被更新。如果有負邊的話，貪心法的過程會發生錯誤，導致得到不正確的答案。
此圖中如果邊 $\delta(B,A)$ 為一負邊，當A被移出集合U中便不會有任何再次被更新的機會，但卻因為這條負邊的關係，導致從$s$到$A$的最短距離並不會被正確更新到！
以上大概就是最短距離的演算法整理，還有一個全點對最短路徑Johnson’s Algorithm，大概就是對任一點做 Bellman-Ford（順便判斷有沒 有負環)，得到點權之後，用調整完的邊權做 V 次 Dijkstra，可以比Floyd-Warshall有更好的表現，到時候看。