--- ###### tags: `2020 師大附中校隊培訓` --- # 最短路徑 ## 2020 師大附中校隊培訓 #### joylintp #### 10.28.2020 --- ## 最短路徑 最短路徑即為兩點間所有路徑中邊權和最小者 最短路徑上不允許存在負環，否則可以經由不斷通過負環讓路徑權重和持續變小 ---- ### 單點源最短路徑 求出一個點到所有點的最短路徑 ### 多點源最短路徑 求出所有點對的最短路徑 ---- ### 鬆弛 ### Relaxation 對於兩個點 $u$、$v$，設其之間的邊權為 $w_{u,v}$ 若起點到它們的距離 $d_u$、$d_v$ 滿足$d_u+w_{u, v}<d_v$， 即可把 $d_v$ 更新成 $d_u+w_{u, v}$，使 $u$ 到 $v$ 的距離變短， 這個動作就叫鬆弛 --- ## Bellman-Ford algorithm * 單點源最短路徑 * 可以有負邊，可判斷負環 ---- ### Bellman-Ford algorithm * 將起點最短路徑長設為 0，其餘長度為無限大 * 枚舉每條邊，嘗試每條邊是否可進行鬆弛 若第 $V$ 次枚舉時仍有邊可以鬆弛，即表示圖中有負環； 否則，表示所有點已為最短路徑 時間複雜度 $O(VE)$ --- ## Dijkstra algorithm * 單點源最短路徑 * 不可有負邊，不可判斷負環 ---- ### Dijkstra algorithm * 將起點最短路徑長設為 0，其餘長度為無限大 * 在所有已找到最短路徑的點中，尋找所有往外的邊中權重最小者延伸 最糟情況下每條邊都需被鬆弛一次 時間複雜度 $O(E\ log\ E)$ ---- ```cpp= cin >> n >> m >> s; for (int i = 1; i <= n; i++) dis[i] = 1e18; dis[s] = 0; int a, b, c; while (m--) cin >> a >> b >> c, edge[a].push_back({b, c}); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, s}); while (!pq.empty()) { int u = pq.top().second, d = pq.top().first; pq.pop(); if (vis[u]) continue; vis[u] = true; for (auto p : edge[u]) if (!vis[p.first] && d + p.second < dis[p.first]) dis[p.first] = d + p.second, pq.push({dis[p.first], p.first}); } for (int i = 1; i <= n; i++) cout << dis[i] << " \n"[i == n]; ``` --- ## Floyd-Warshall algorithm * 多點源最短路徑 * 可以有負邊，可判斷負環 ---- ### Floyd-Warshall algorithm ### 動態規劃 * 令 $dp_{i,j}$ 為 $i$ 到 $j$ 的最短路徑長， * 將 $dp_{i, j}$ 設為 $w_{i,j}$，$dp_{i, i}$ 設為 0 * $dp_{i, j} = min(dp_{i,k}+dp_{k, j}, dp_{i, j})$ 時間複雜度 $O(V^3)$ ---- ```cpp= cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[i][j] = 2e18; for (int i = 1; i <= n; i++) dis[i][i] = 0; int u, v, w; while (m--) cin >> u >> v >> w, dis[u][v] = min(dis[u][v], w); for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); for (int i = 1; i <= n; i++) if (dis[i][i] < 0) cout << "-1\n"; for (int i = 1; i <= n; i++, cout << '\n') for (int j = 1; j <= n; j++) cout << dis[i][j] << ' '; ``` ---