一. 單源最短路：Dijkstra 算法
1.套路
1.Dijkstra 算法介紹
(1)定義 g[i][j] 表示節點 i 到節點 j 這條邊的邊權。如果沒有 i 到 j 的邊，則 g[i][j]=∞。
(2)定義 dis[i] 表示起點 k 到節點 i 的最短路長度，一開始 dis[k]=0，其余 dis[i]=∞ 表示尚未計算出。
(3)我們的目標是計算出最終的 dis 數組。
- 首先更新起點 k 到其鄰居 y 的最短路，即更新
dis[y]為g[k][y]。 - 然后取除了起點 k 以外的
dis[i]的最小值(貪心)，假設最小值對應的節點是 3。此時可以斷言：dis[3]已經是 k 到 3 的最短路長度，不可能有其它 k 到 3 的路徑更短！反證法：假設存在更短的路徑，那我們一定會從 k 出發經過一個點 u，它的dis[u]比dis[3]還要小，然后再經過一些邊到達 3，得到更小的dis[3]。但dis[3]已經是最小的了，并且圖中沒有負數邊權，所以 u 是不存在的，矛盾。故原命題成立，此時我們得到了dis[3]的最終值。 - 用節點 3 到其鄰居 y 的邊權
g[3][y]更新dis[y]：如果dis[3]+g[3][y]<dis[y]，那么更新dis[y]為dis[3]+g[3][y]，否則不更新。 - 然后取除了節點 k,3 以外的
dis[i]的最小值，重復上述過程。 - 由數學歸納法可知，這一做法可以得到每個點的最短路。當所有點的最短路都已確定時，算法結束。
2.模版
// 返回從起點start到每個點的最短路徑dis,如果節點x不可達，則dis[x]=LLong_max
// 要求：沒有負數邊權
// 時間復雜度O(n+mlogm),注意堆中有O(m)個元素(懶更新所有邊進入),獲取堆元素每次為(logm)
// 兩個節點之間也可能有多條邊不用更改代碼，同樣滿足
typedef long long ll;
typedef pair<int,long long> PIL;
typedef pair<long long,int> PLI;
vector<ll> shortPathDijkstra(int n,vector<vector<int>>& edges,int start){// 注:如果節點編號從1開始(而不是從0開始)，可以把n加1(g初始化,dis初始化以及最終dis結果不包括0元素)vector<vector<PIL>> g(n);for(auto& e:edges){int x=e[0],y=e[1],wt=e[2];g[x].push_back({y,wt});// g[y].push_back({x,wt}); // 無向圖}vector<ll> dis(n,LLONG_MAX);// 最短距離小頂堆priority_queue<PLI,vector<PLI>,greater<>> pq;dis[start]=0;pq.push({0,start});while(!pq.empty()){auto t=pq.top();pq.pop();ll dis_x=t.first;int x=t.second;// 懶刪除if(dis_x>dis[x]){continue;}for(auto& t2:g[x]){int y=t2.first;ll wt=t2.second;ll newdis=dis_x+wt;if(newdis<dis[y]){dis[y]=newdis;// 懶更新堆，先不更新堆中最短距離，而是全都入堆，出堆時再判斷pq.push({newdis,y});}}}return dis;
}
2.網格圖模版(無鄰接表，dis二維數組，堆中tuple三元組):
class Solution {
public:int n, m;typedef long long ll;typedef tuple<long long, int, int> TLII;vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};bool inMap(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }int minTimeToReach(vector<vector<int>>& moveTime) {n = moveTime.size(), m = moveTime[0].size();vector<vector<ll>> dis(n, vector<ll>(m, LLONG_MAX));priority_queue<TLII, vector<TLII>, greater<>> pq;dis[0][0] = 0;pq.push({0, 0, 0});while (!pq.empty()) {auto t = pq.top();pq.pop();ll dis_xy = get<0>(t);int x = get<1>(t), y = get<2>(t);if (dis_xy > dis[x][y])continue;for (int i = 0; i < 4; ++i) {int nx = x + dx[i], ny = y + dy[i];if (!inMap(nx, ny))continue;ll newdis = max(dis_xy, 1LL * moveTime[nx][ny]) + 1;if (newdis < dis[nx][ny]) {dis[nx][ny] = newdis;pq.push({newdis, nx, ny});}}}return dis[n - 1][m - 1];}
};
2.題目描述
3.學習經驗
1. 743. 網絡延遲時間(中等)
743. 網絡延遲時間 - 力扣（LeetCode）
思想
1.有?n?個網絡節點，標記為?1?到?n。
給你一個列表?times，表示信號經過?有向?邊的傳遞時間。?times[i] = (ui, vi, wi)，其中?ui?是源節點，vi?是目標節點，?wi?是一個信號從源節點傳遞到目標節點的時間。
現在，從某個節點?K?發出一個信號。需要多久才能使所有節點都收到信號？如果不能使所有節點收到信號，返回?-1?。
2.模版題，時間即邊權，答案為起點到其他點的最大距離
代碼
class Solution {
public:typedef long long ll;typedef pair<int, long long> PIL;typedef pair<long long, int> PLI;int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<PIL>> g(n + 1);for (auto& e : times) {int u = e[0], v = e[1], wt = e[2];g[u].push_back({v, wt});}vector<ll> dis(n + 1, LLONG_MAX);priority_queue<PLI, vector<PLI>, greater<>> pq;dis[k] = 0;pq.push({0, k});while (!pq.empty()) {auto t = pq.top();pq.pop();int u = t.second;ll dis_u = t.first;if (dis_u > dis[u])continue;for (auto& t2 : g[u]) {int y = t2.first;ll wt = t2.second;if (dis_u + wt < dis[y]) {dis[y] = dis_u + wt;pq.push({dis[y], y});}}}ll res = -1;for (int i = 1; i <= n; ++i) {if (dis[i] == LLONG_MAX)return -1;res = max(res, dis[i]);}return res;}
};
2. 3341. 到達最后一個房間的最少時間I(中等)
3341. 到達最后一個房間的最少時間 I - 力扣（LeetCode）
思想
1.有一個地窖，地窖中有?n x m?個房間，它們呈網格狀排布。
給你一個大小為?n x m?的二維數組?moveTime?，其中?moveTime[i][j]?表示房間開啟并可達所需的?最小?秒數。你在時刻?t = 0?時從房間?(0, 0)?出發，每次可以移動到?相鄰?的一個房間。在?相鄰?房間之間移動需要的時間為 1 秒。
請你返回到達房間?(n - 1, m - 1)?所需要的?最少?時間。
如果兩個房間有一條公共邊（可以是水平的也可以是豎直的），那么我們稱這兩個房間是?相鄰?的。
2.網格圖Dijkstra,不再是單個頂點編號，而是一個位置，所以dis變成二維數組，堆中為三元組，可以用tuple<ll,int,int>,但獲取元素不再是first,second,而是get<0>(t),get<1>(t),get<2>(t)
3.多了個限制條件:“其中?moveTime[i][j]?表示房間開啟并可達所需的?最小?秒數”,所以從(x,y)到(nx,ny)的最少秒數為max(dis_xy,moveTime[nx][ny])+1
代碼
class Solution {
public:int n, m;typedef long long ll;typedef tuple<long long, int, int> TLII;vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};bool inMap(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }int minTimeToReach(vector<vector<int>>& moveTime) {n = moveTime.size(), m = moveTime[0].size();vector<vector<ll>> dis(n, vector<ll>(m, LLONG_MAX));priority_queue<TLII, vector<TLII>, greater<>> pq;dis[0][0] = 0;pq.push({0, 0, 0});while (!pq.empty()) {auto t = pq.top();pq.pop();ll dis_xy = get<0>(t);int x = get<1>(t), y = get<2>(t);if (dis_xy > dis[x][y])continue;for (int i = 0; i < 4; ++i) {int nx = x + dx[i], ny = y + dy[i];if (!inMap(nx, ny))continue;ll newdis = max(dis_xy, 1LL * moveTime[nx][ny]) + 1;if (newdis < dis[nx][ny]) {dis[nx][ny] = newdis;pq.push({newdis, nx, ny});}}}return dis[n - 1][m - 1];}
};
3. 3112. 訪問消失節點的最少時間(中等)
3112. 訪問消失節點的最少時間 - 力扣（LeetCode）
思想
1.給你一個二維數組?edges?表示一個?n?個點的無向圖，其中?edges[i] = [ui, vi, lengthi]?表示節點?ui?和節點?vi?之間有一條需要?lengthi?單位時間通過的無向邊。
同時給你一個數組?disappear?，其中?disappear[i]?表示節點?i?從圖中消失的時間點，在那一刻及以后，你無法再訪問這個節點。
注意，圖有可能一開始是不連通的，兩個節點之間也可能有多條邊。
請你返回數組?answer?，answer[i]?表示從節點?0?到節點?i?需要的?最少?單位時間。如果從節點?0?出發?無法?到達節點?i?，那么?answer[i]?為?-1?。
2.從x->y,獲得到達y的newdis后，先判斷是否在disappear[y]之前即可
代碼
class Solution {
public:typedef pair<int, int> PII;vector<int> minimumTime(int n, vector<vector<int>>& edges,vector<int>& disappear) {vector<vector<PII>> g(n);for (auto& e : edges) {int u = e[0], v = e[1], w = e[2];g[u].push_back({v, w});g[v].push_back({u, w});}priority_queue<PII, vector<PII>, greater<>> pq;vector<int> dis(n, INT_MAX);dis[0] = 0;pq.push({0, 0});while (!pq.empty()) {auto t = pq.top();pq.pop();int dis_u = t.first;int u = t.second;if (dis_u > dis[u])continue;for (auto& t2 : g[u]) {int v = t2.first;int w = t2.second;int newdis = dis_u + w;if (newdis < disappear[v] && newdis < dis[v]) {dis[v] = newdis;pq.push({newdis, v});}}}for (int i = 0; i < n; ++i) {if (dis[i] == INT_MAX)dis[i] = -1;}return dis;}
};
二. 全源最短路：Floyd 算法
1.套路
1.Floyd 算法本質是三維 DP,理解:
f[k][i][j]表示i和j之間可以通過編號為1-k的節點集的最短路徑
初值f[0][i][j]為原圖的鄰接矩陣
則f[k][i][j]:
- (1)從
f[k-1][i][j]轉移過來，表示不經過k - (2)從
f[k-1][i][k]+f[k-1][k][j]轉移過來，表示經過k
所以,f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])
發現最外層f[k]只由f[k-1]轉移，所以可以覆蓋，所以代碼中只有寫二維數組，但最外層遍歷是k
![[floyd三維DP.png]]
2.圖解為什么遍歷時k在最外層，不能再最里層
(1)在最里層的反例(當前路徑需要之后遍歷的路徑轉移過來，即轉移順序與遍歷順序相斥):
![[floyd的k在內層反例.png]]
(2)k在最外層的更新邏輯(交換兩個k作對比):
![[floyd的k在最外層.png]]
3.模版:
// 返回一個二維列表(鄰接矩陣)，其中(i,j)這一項表示從i到j的最短路長度
// 如果無法從i到j，則最短路長度為LLONG_MAX/2(防止加法溢出)
// 允許負數邊權
// 如果計算完畢后，存在i，使得從i到i的最短路長度小于0(負環找不到最短路，無限更新),說明圖中有負環
// 節點編號從0到n-1
// 時間復雜度O(nn^3+m),其中m是edges的長度
typedef long long ll;
const ll INF=LLONG_MAX/2; // 防止加法溢出
vector<vector<ll>> shortestPathFloyd(int n,vector<vector<int>>& edges){vector<vector<ll>> f(n,vector<ll>(n,INF));for(int i=0;i<n;++i){f[i][i]=0;}for(auto& e:edges){int x=e[0],y=e[1];ll w=e[2];f[x][y]=min(f[x][y],w); // 如果有重邊，取最小值f[y][x]=min(f[y][x],w); // 無向圖}// 三層遍歷，最外層kfor(int k=0;k<n;++k){for(int i=0;i<n;++i){// 針對稀疏圖的優化if(f[i][k]==INF){continue;}for(int j=0;j<n;++j){f[i][j]=min(f[i][j],f[i][k]+f[k][j]);}}}/*// 檢查負環for(int i=0;i<n;++i){if(f[i][i]<0){// 存在負環}}*/return f;
}
2.題目描述
3.學習經驗
1. 1334. 閾值距離內鄰居最少的城市(中等)
1334. 閾值距離內鄰居最少的城市 - 力扣（LeetCode）
思想
1.有?n?個城市，按從?0?到?n-1?編號。給你一個邊數組?edges，其中?edges[i] = [fromi, toi, weighti]?代表?fromi?和?toi?兩個城市之間的雙向加權邊，距離閾值是一個整數?distanceThreshold。
返回在路徑距離限制為?distanceThreshold?以內可到達城市最少的城市。如果有多個這樣的城市，則返回編號最大的城市。
注意，連接城市?i?和?j?的路徑的距離等于沿該路徑的所有邊的權重之和。
2.模版題
代碼
class Solution {
public:typedef long long ll;const ll INF = LLONG_MAX / 2;int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {vector<vector<ll>> f(n, vector<ll>(n, INF));for (int i = 0; i < n; ++i)f[i][i] = 0;for (auto& e : edges) {int x = e[0], y = e[1], w = e[2];f[x][y] = min(f[x][y], 1LL * w);f[y][x] = min(f[y][x], 1LL * w);}for (int k = 0; k < n; ++k) {for (int i = 0; i < n; ++i) {if (f[i][k] == INF)continue;for (int j = 0; j < n; ++j) {f[i][j] = min(f[i][j], f[i][k] + f[k][j]);}}}int res = -1, resCnt = INT_MAX;// 倒序保證編號最大for (int i = n - 1; i >= 0; --i) {int cnt = 0;for (int j = 0; j < n; ++j) {if (f[i][j] <= distanceThreshold)++cnt;}if (cnt < resCnt) {resCnt = cnt;res = i;}}return res;}
};
2. 2642. 設計可以求最短路徑的圖類(困難,學習)
2642. 設計可以求最短路徑的圖類 - 力扣（LeetCode）
思想
1.給你一個有?n?個節點的?有向帶權?圖，節點編號為?0?到?n - 1?。圖中的初始邊用數組?edges?表示，其中?edges[i] = [fromi, toi, edgeCosti]?表示從?fromi?到?toi?有一條代價為?edgeCosti?的邊。
請你實現一個?Graph?類：
Graph(int n, int[][] edges)?初始化圖有?n?個節點，并輸入初始邊。addEdge(int[] edge)?向邊集中添加一條邊，其中?edge = [from, to, edgeCost]?。數據保證添加這條邊之前對應的兩個節點之間沒有有向邊。int shortestPath(int node1, int node2)?返回從節點?node1?到?node2?的路徑?最小?代價。如果路徑不存在，返回?-1?。一條路徑的代價是路徑中所有邊代價之和。
2.首先能想到Dijkstra,初始化要O(n+m),addEdge要O(1),查詢要O(n+mlogm)
學習Floyd,初始化要O(n3+m),**`addEdge`要O(n2),但是查詢只要O(1)**
3.重點學習addEdge,即新增一條x->y,它會影響所有i->j的最短路，會出現i->…x->y…->j,所以二重循環更新
4.注意因為有f[i][x] + w + f[y][j],所以INF開INT_MAX / 3
代碼
class Graph {
public:vector<vector<int>> f;const int INF = INT_MAX / 3;int len;Graph(int n, vector<vector<int>>& edges) {len = n;f.assign(n, vector<int>(n, INF));for (int i = 0; i < n; ++i)f[i][i] = 0;for (auto& e : edges) {int x = e[0], y = e[1], w = e[2];f[x][y] = min(f[x][y], w);}for (int k = 0; k < n; ++k) {for (int i = 0; i < n; ++i) {if (f[i][k] == INF)continue;for (int j = 0; j < n; ++j) {f[i][j] = min(f[i][j], f[i][k] + f[k][j]);}}}}void addEdge(vector<int> edge) {int x = edge[0], y = edge[1], w = edge[2];if (w >= f[x][y]) { // 無需更新return;}for (int i = 0; i < len; ++i) {for (int j = 0; j < len; ++j) {f[i][j] = min(f[i][j], f[i][x] + w + f[y][j]);}}}int shortestPath(int node1, int node2) {if (f[node1][node2] == INF)return -1;elsereturn f[node1][node2];}
};/*** Your Graph object will be instantiated and called as such:* Graph* obj = new Graph(n, edges);* obj->addEdge(edge);* int param_2 = obj->shortestPath(node1,node2);*/
3. 1462. 課程表IV(中等，floyd可以作為初始化，多次查詢判斷多源點是否可達，不是只能求最短距離)
思想
1.你總共需要上?numCourses?門課，課程編號依次為?0?到?numCourses-1?。你會得到一個數組?prerequisite?，其中?prerequisites[i] = [ai, bi]?表示如果你想選?bi?課程，你?必須?先選?ai?課程。
- 有的課會有直接的先修課程，比如如果想上課程?
1?，你必須先上課程?0?，那么會以?[0,1]?數對的形式給出先修課程數對。
先決條件也可以是?間接?的。如果課程?a?是課程?b?的先決條件，課程?b?是課程?c?的先決條件，那么課程?a?就是課程?c?的先決條件。
你也得到一個數組?queries?，其中?queries[j] = [uj, vj]。對于第?j?個查詢，您應該回答課程?uj?是否是課程?vj?的先決條件。
返回一個布爾數組?answer?，其中?answer[j]?是第?j?個查詢的答案。
2.首先，這一問乍一眼看是拓撲排序，但拓撲排序是獲得個順序，而此題核心在于多次查詢兩個點是否可達，要簡化查詢的時間。從而多源點想到floyd,其作為初始化時間復雜度為O(n^3),但是查詢只需O(1),所以非常合適，將邊權簡單設置為1即可，只要最短距離不是INF,說明可達。
代碼
class Solution {
public:const int INF = INT_MAX / 2;vector<bool> checkIfPrerequisite(int numCourses,vector<vector<int>>& prerequisites,vector<vector<int>>& queries) {vector<vector<int>> f(numCourses, vector<int>(numCourses, INF));for (int i = 0; i < numCourses; ++i) {f[i][i] = 0;}for (auto& e : prerequisites) {int x = e[0], y = e[1];f[x][y] = 1; // 假設邊權位1}for (int k = 0; k < numCourses; ++k) {for (int i = 0; i < numCourses; ++i) {if (f[i][k] == INF)continue;for (int j = 0; j < numCourses; ++j) {f[i][j] = min(f[i][j], f[i][k] + f[k][j]);}}}vector<bool> res;for (auto& q : queries) {int x = q[0], y = q[1];// 利用floyd求出來的f數組判斷是否可達if (f[x][y] == INF)res.push_back(false);elseres.push_back(true);}return res;}
};
