最後更新日期 2024 / 01 / 01

很多最短路演算法

Dijkstra

概念

每次選擇最近的節點
嘗試透過該節點來更新相鄰節點距離

實作

將所有節點距離初始化為 ( 起點為 0 )
選擇目前距離起點最近的節點
如果目前節點距離加上相鄰節點與目前節點距離小於起點到相鄰節點的距離就更新

程式碼

for (int i = 1; i <= n; i++) distance[i] = INF;
distance[x] = 0;
q.push({0, x});
while (!q.empty()) {
	int a = q.top().second; q.pop();
    // 絕對不會更新到的話直接 continue 掉
    if (a.first > dist[now.second]) continue;
	for (auto u : adj[a]) {
		int b = u.first, w = u.second;
		if (distance[a] + w < distance[b]) {
			distance[b] = distance[a] + w;
            // 因為要讓距離小的排在前面所以加負號
			q.push({-distance[b], b});
		}
	}
}

Floyd-WarShall

概念

這個演算法是由某個 DP 概念延伸出來的
最初的轉移式大概長這樣

定義:

dp[k][i][j]ij 的最短距離,且只能經過額外的 k 個點

轉移式:

dp(i,j,k)=min(dp(i,j,k1),dp(i,k,k1)+dp(k,j,k1))

實作

依照 DP 轉移式枚舉每個點做轉移就好了
實作上由於 k 是按照順序轉移的所以可以把空間壓到二維
記得要注意迴圈是由外而內順序是 kij

程式碼

for (int k = 1; k <= n; k++) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}
}

奇怪的小技巧

如果不小心忘記寫成 i j k 的話只要做三次就會對了
2019 年的某篇論文上提到了這點

判斷負環

如果任一個 dist[i][i]<0 若且唯若存在負環
代表有一個點自己繞一圈回到自己距離小於 0
但如果是無向圖的話的負環就很難判斷了

Bellman-Ford

概念

對於每個邊嘗試更新連接的兩個點對於起點的距離

實作

重複 n-1 次嘗試更新所有的邊

程式碼

for (int i = 1; i <= n; i++) dist[i] = INF;
	dist[x] = 0;
	for (int i = 1; i <= n-1; i++) {
		for (auto e : edges) {
			int a, b, w;
			tie(a, b, w) = e;
			dist[b] = min(dist[b], dist[a] + w);
		}
	}
}

判斷負環

如果更新了 n-1 次還能繼續更新
代表這張圖存在負環

結論

看完這些之後
想必一定有人會覺得「為什麼要學這麼多種最短路演算法」
原因很簡單,因為這些演算法各自有不同的特性與效率
所以需要適時挑選適合的演算法來使用

不過比較值得注意的是
事實上如果要求多源最短路的話
枚舉每個點做 Dijkstra 甚至比 Floyd-Warshall 還快

Bellman-Ford Dijkstra Floyd-Warshall
類型 單點源 單點源 全點對
限制 任意圖 無負邊 任意圖
時間複雜度 O(VE) O(ElogE) O(V3)
用途 檢查負環 快速單點源 負邊全點對

推薦文章

圖論入門

首先 我們要先來了解什麼是圖簡單來說 圖 Graph 就是由多個節點 Node 並透過邊 Edge 連結成的我們像是下面的示意圖在知道圖是什麼之後 我們要來看的是如何在 C++ 中儲存一張圖在大部分的情況下 我們會以節點關係來儲存一張圖像是上面那張圖片的範例 我們知道節點 1 會連接到節點 2 跟 3 節點 2 會連接到節點 1 跟 3 節點 3 會連接到節點 2 跟 4 節點 4 會連接到節點 3 跟 5 節點 5 會連接到節點 4 也就是說 我們實際上要存的資料大概長這樣:1 - 2, 32 - 1, 33 - 2, 44 - 3, 55 - 4C++ 內可以使用傳統陣列套 vector 來實現cpp MAXN 最大節點數量vectorint graphMAXN; 下面的操作就是相當於我們從節點 1 建立了兩條邊分別指向 2 跟 3graph1.pushback2;graph1.pushback3;在很多的情境下 我們會需要拜訪整張圖上面的所有節點來得知一些資訊這邊會簡單的介紹一下 DFS 深度優先搜尋 演算法的作法 這個演算法就是利用遞迴的特性遍歷整張圖這個演算法會儘可能深的搜尋圖的分支 當節點的所有邊都已經被搜尋過 則會回溯到上個節點 這個過程會一直重複到搜尋完整張圖為止程式碼應該不難理解 直截來看看吧:cppvectorint graphMAXN; 存圖bool visMAXN; 紀錄哪些節點拜訪過void dfsint v { 枚舉每一個 v 可以走到的節點 for int u : graphv { 如果走過就略過 if visu continue; 標記為走過 visu = true; 造放進節點 u dfsu; }}樹其實就是圖的一種 有一些特性:- 不存在環- 每個節點均可以走到其他每個節點- 若有 n 個節點,邊就是 n-1 條這邊先補充一下 環就是指像是最上面的示意圖 1 - 2 - 3 那部分的結構然後樹的其他部分都跟圖差不多 不過 DFS 可以寫的比圖簡單cppvoid dfsint v, int p { 枚舉每一個 v 可以走到的節點 for int u : graphv { 不能走回上個節點 if u == p continue; 造放進節點 u dfsu, v; }}這裡是一些簡單的練習題:- CSES Building Roads- CSES Message Route或者你也可以在這邊了解一些更進階的內容:- 最短路演算法

Algorithms

C++ 常見 STL 教學

pair 是一種可以儲存兩個元素的資料結構通常用來儲存二維座標或者是陣列的 index 與 value 而且常數較小 如果用 array vector 替代有些題目真的會被卡 TLEcpp 宣告一個第一個欄位為 1 第二個欄位為 5 的 pair 在一些 c++ 版本較舊的環境下要使用 makepair1, 5pairint, int pos = {1, 5}; 取得第一個欄位的值cout pos.first endl; 取得第二個欄位的值cout pos.second endl; 將 pos 的第一個欄位的 1 改成 2pos.first = 2; 將 pos 的第二個欄位的 5 改成 4pos.second = 4;在比較兩個 pair 時會先比第一個元素 如果第一個元素相同才會比第二個元素跟傳統陣列差不多 不過長度是可變的 會因為加入更多元素讓 vector 變得更長不用多說了吧 就是可以像陣列一樣儲存 n 個元素cpp 直接宣告 vector 的方式vectorint v1; 宣告長度為 n 的 vectorvectorint v2n; 宣告長度為 n 且每個元素都是 5 的 vectorvectorint v3n, 5; 宣告一個有元素 {1, 2, 3, 4} 的 vectorvectorint v4 = {1, 2, 3, 4} 宣告一個跟其他 vector 一樣的 vector 複製vectorint v5v4; 加入元素在尾端v1.pushback7; 從尾端移除元素v1.popback; 存取 vector 中的某一項cout v42 endl; 取得大小cout v2.size endl;從第一個元素開始比較 如果相同就繼續往後比 直到第一個不同為止像是一個排隊的隊伍 可以從一端進入 從另一端離開 也就是先進去的會先離開大部分情況用來實作一些較複雜的演算法 比如 BFS、拓撲排序等等cpp 宣告一個 queuequeueint q; 將元素 5 推入 queue 後端q.push5; 取得 queue 前端的元素cout q.front endl; 取得 queue 後端的元素cout q.back endl; 將隊伍前端的元素彈出移除q.pop; 檢查 queue 是否為空if q.empty { cout "empty" endl;} 取得 queue 的大小cout q.size endl;類似於一疊盤子 最後放上去的盤子會最先被取走 而你不能從中間拿走盤子 也就是說後進去的會先出去stack 常用來會處理一些匹配類問題 或者是模擬遞迴 更進階一點還有單調堆疊之類的玩法cpp 宣告一個 stackstackint stk; 將元素 3 推入 stackstk.push3; 從 stack 頂端取出元素cout stk.top endl; 將 stack 頂端的元素彈出移除stk.pop; 檢查 stack 是否為空if stk.empty { cout "empty" endl;} 取得 stack 的大小cout stk.size endl;就是集合的意思 用來儲存不重複的元素 並會按照元素的大小自動排序主要用於快速插入和查找元素cpp 宣告一個 setsetint st; 插入元素st.insert5;st.insert3;st.insert7; 檢查 set 是否包含某元素if st.find3 = st.end { cout "set contains 3" endl;} else { cout "set does not contain 3" endl;} 刪除元素st.erase5; 遍歷 set 中的元素for int e : st { cout e " ";} 取得 set 的大小cout st.size endl; 取得 set 的第一項 因為回傳的是 iterator 所以要加 cout st.begin endl; 取得 set 的最後一項 由於 back 是開區間所以要 -1cout --st.end endl;語法根陣列有點像 不過可以接受整數以外的型態來當作索引值有些時候需要使用負數、非常大的數字、字串等等來當索引值 map 就會是一個很方便的工具cpp 宣告一個以 string 為索引,int 為值的 mapmapstring, int mp; 把字串對應到數字mp"one" = 1;mp"two" = 2;mp"three" = 3; 輸出 one 的值cout mp"one" endl; 在 map 中刪除 onemp.erase"one"; 遍歷 mapfor auto key, value : mp { cout key ", " value endl;} 取得 map 的大小cout mp.size endl;又稱為 heap 可以支援快速地插入及查詢最大最小值很常使用在一些複雜的演算法內 比如最短路徑、最小生成樹等等cpp 宣告一個 priority queuepriorityqueueint pq; 宣告一個 priority queue 並且頂部為最小值priorityqueueint, vectorint, greaterint pq; 插入元素pq.push3;pq.push1;pq.push5; 取得頂端的元素最大值cout pq.top endl; 移除頂端的元素pq.pop; 檢查 priority queue 是否為空if pq.empty { cout "empty" endl;} 取得 priority queue 的大小cout pq.size endl;

Algorithms

題解 CSES Restaurant Customers

給你 n 位客人的進入和離開餐廳的時間 輸出最多同時有幾位客人同時在餐廳- n le 2 times 10^5把每個人加入時間和離開的時間分別看成兩個時間點 並把所有時間點加入陣列後一起排序 然後用一個變數來維護目前餐廳人數 每次遇到加入就增加 反之遇到離開就減少 維護中遇到的最大值就是答案了 時間複雜度:Oncpp using namespace std; signed main { int n; cin n; vectorpii v; for int i = 0; i n; i++ { int s, t; cin s t; v.pushback{s, true}; v.pushback{t, false}; } sortv.begin, v.end; int cur = 0; int ans = 0; for auto e : v { if e.ss == true cur++; else cur--; ans = maxcur, ans; } cout ans endl;}

CSES