題目鏈接

743. 網絡延遲時間

題目描述

有 N 個網絡節點，標記為 1 到 N。

給定一個列表 times，表示信號經過有向邊的傳遞時間。 times[i] = (u, v, w)，其中 u 是源節點，v 是目標節點， w 是一個信號從源節點傳遞到目標節點的時間。

現在，我們從某個節點 K 發出一個信號。需要多久才能使所有節點都收到信號？如果不能使所有節點收到信號，返回 -1。

樣例

輸入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2輸出：2

數據范圍

N 的范圍在 [1, 100] 之間。
K 的范圍在 [1, N] 之間。
times 的長度在 [1, 6000] 之間。
所有的邊 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。

算法

圖論的題目一般是 3 步，建圖 -> 圖論算法 -> 后處理。

本題也是一樣的思路：先建鄰接表，然后求單源最短路，然后根據找到的各個點的最短路，找到從起始點出發可以到達的最遠的距離。

一般比較難的題目難點都是在建圖這一步。有的是非常隱晦的圖論問題，想不到建圖處理，例如 127. 單詞接龍；有的是建圖過程中 corner case 非常多，很容易漏，例如 444. 序列重建。成功完成建圖之后(一般是建鄰接表比較多)，之后的圖論算法就比較模板化了。

當邊的權都相同時，求最短路直接一趟 BFS就可以，典型題目 1091. 二進制矩陣中的最短路徑。當邊權不同的時候有以下幾種。

dijkstra 數組實現: O(E + V^2)，有貪心思想，不能處理負權
dijkstra 堆實現: O(ElogV + VlogV)，有貪心思想，不能處理負權
bellman ford: O(VE), 可以處理負權，可以檢測負環
spfa: O(VE), bellman ford 的優化, 可以處理負權，可以檢測負環
floyd: O(V^3) 可以把所有點之間的最短路徑求出，如果求多源最短路，時間復雜度可攤銷

如果沒有負權的話，一般使用 dijkstra 最好。

代碼(c++)

代碼框架就是 建立鄰接表 -> 單源最短路算法 -> 后處理

單源最短路算法的 5 種算法都是模板，對應的實現在引申部分

class Solution { public:int networkDelayTime(vector<vector<int>>& times, int N, int K) {vector<vector<vector<int> > > g(N + 1);for(vector<int> &edge: times)g[edge[0]].push_back({edge[1], edge[2]});// 求帶權鄰接表的最短路vector<int> d = dijkstra_array(g, K, N);// vector<int> d = dijkstra_heap(g, K, N);// vector<int> d = bellman_ford(g, K, N);// vector<int> d = spfa(g, K, N);// vector<int> d = floyd(g, K, N);int res = 0;for(int i = 1; i <= N; i++){if(d[i] == -1)return -1;res = max(res, d[i]);}return res;} };

引申: 權鄰接表的單源最短路模板代碼

接口：

// g 是建好的鄰接表，start 是起始點，N 是節點個數； 返回各個點到 start 的最短路徑 vector<int> shortest_path(vector<vector<vector<int> > >& g, int start, int N)；

5個算法的接口都一樣，下面是對應的模板代碼，原理部分沒有展開。

如果能夠將問題轉化成模板問題，再套模板就輕松愉快了。這個有點類似下棋或者炒菜的背譜，只會背譜肯定是不好的，但是背譜可以快速下出挑不出什么毛病的棋，快速炒出80分的菜。

1. dijkstra 數組實現

vector<int> dijkstra_array(vector<vector<vector<int> > >& g, int start, int N) {// dijkstra 數組實現 O(E + V^2)// 不能有負權// 存放 start 到各個點的最短路徑vector<int> d(N + 1, -1);d[start] = 0;// 記錄是否找到 start 到該點的最短路徑vector<bool> visited(N + 1, false);visited[start] = true;// 初始化 start 到各個點的距離for(vector<int> son: g[start])d[son[0]] = son[1];for(int cnt = 1; cnt <= N - 1; ++cnt){int min_val = INT_MAX / 2, min_idx = 0;// 遍歷所有節點，找到離 start 最近的節點for(int i = 1; i <= N; ++i){if(d[i] != -1 && !visited[i] && d[i] < min_val){min_idx = i;min_val = d[i];}}// 標記離 start 最近距離節點已經找到visited[min_idx] = true;// 根據剛剛找到的距離 start 最短的節點，// 通過該節點更新 start 與其它節點的距離for(vector<int> son: g[min_idx]){if(d[son[0]] != -1) // 之前路徑與當前更新路徑的最小值d[son[0]] = min(d[son[0]], min_val + son[1]);else // 該節點第一次訪問，直接更新d[son[0]] = min_val + son[1];}}return d; }

2. dijkstra 堆實現

vector<int> dijkstra_heap(vector<vector<vector<int> > >& g, int start, int N) {// dijkstra 堆實現 O(ElogV + VlogV)// 不能有負權// 存放 start 到各個點的最短路徑vector<int> d(N + 1, INT_MAX / 2);d[start] = 0;priority_queue<vector<int>, vector<vector<int> >, Cmp> pq; // 隊列元素 (節點編號，到 start 的距離)pq.push({start, 0});while(!pq.empty()){vector<int> cur = pq.top();pq.pop();if(d[cur[0]] < cur[1]) continue;for(vector<int> son: g[cur[0]]){if(d[son[0]] <= d[cur[0]] + son[1]) continue;d[son[0]] = d[cur[0]] + son[1];pq.push({son[0], d[son[0]]});}}return d; }struct Cmp {bool operator() (const vector<int>& item1, const vector<int>& item2){return item1[1] > item2[1]; // 最小堆} };

3. bellman ford

松弛操作，它的原理是著名的定理：“三角形兩邊之和大于第三邊”

vector<int> bellman_ford(vector<vector<vector<int> > >& g, int start, int N) {// bellman ford O(VE)// 可以檢測負環vector<int> d(N + 1, -1);d[start] = 0;// 進行 N - 1 輪松弛// 因為任意兩點之間最短路最多包含 N - 1 條邊for(int cnt = 1; cnt <= N - 1; ++cnt){// u: 源節點，v: 子節點, w: uv 的權for(int u = 1; u <= N; ++u){if(d[u] == -1) continue;for(vector<int> &son: g[u]){int v = son[0], w = son[1];// 判斷能否通過 u -> v 縮短 d[v] (松弛)if(d[u] + w < d[v] || d[v] == -1)d[v] = d[u] + w;}}}/* 可以檢測負環for(int u = 1; u <= N; ++u){for(vector<int> &son: g[u]){int v = son[0], w = son[1];if(d[u] + w < d[v])// 有負環}}*/return d; }

4. spfa

SPFA算法的基本思想：在Bellman-Ford算法中，很多松弛操作其實都是沒有必要的，例如對于一條從 x 到 y 的邊，如果連 x 都還沒被松弛，那 y 肯定也還不能被 x 松弛。用一個隊列來存儲已經被松弛過的點，然后用隊列里的點去松弛其他點，就可以避免用一個還沒有被松弛的點去松弛另外的點。

vector<int> spfa(vector<vector<vector<int> > >& g, int start, int N) {// 與 bellman ford 相同, O(VE)// 可以檢測負環vector<int> d(N + 1, -1);d[start] = 0;queue<int, list<int> > q;q.push(start);// 記錄每個點到 start 的節點個數vector<int> cnt(N + 1, 0);cnt[start] = 1;while(!q.empty()){int cur = q.front();q.pop();for(vector<int> &son: g[cur]){if(d[son[0]] == -1 || d[son[0]] > d[cur] + son[1]){cnt[son[0]] = cnt[cur] + 1;if(cnt[son[0]] > N) return d; // 若 son 到 start 的節點個數大于 N 了說明有負環// 當最短距離發生變化且不在隊列中時，將該節點加入隊列d[son[0]] = d[cur] + son[1];q.push(son[0]);}}}return d; }

5. floyd

vector<int> floyd(vector<vector<vector<int> > >& g, int start, int N) {// floyd 需要鄰接矩陣 O(V^3)// 可以做多源最短路vector<vector<int> > adj_matrix(N + 1, vector<int>(N + 1, -1));for(int i = 1; i <= N; ++i)adj_matrix[i][i] = 0;for(int u = 1; u <= N; ++u)for(vector<int> son: g[u])adj_matrix[u][son[0]] = son[1];// 遍歷所有節點，其中 k 是用于松弛的點for(int k = 1; k <= N; ++k)for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)// 使用 k 松弛 i -> j 的最短路徑if(adj_matrix[i][k] != -1 && adj_matrix[k][j] != -1){if(adj_matrix[i][j] != -1)adj_matrix[i][j] = min(adj_matrix[i][j], adj_matrix[i][k] + adj_matrix[k][j]);elseadj_matrix[i][j] = adj_matrix[i][k] + adj_matrix[k][j];}vector<int> d(N + 1, -1);for(int i = 1; i <= N; ++i)d[i] = adj_matrix[start][i];return d; }

總結

以上是生活随笔為你收集整理的邻接矩阵和邻接表_[力扣743] 带权邻接表的单源最短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。