743. Network Delay Time

方法1: DijkstraComplexity 方法2: Bellman-Ford易错点Complexity 方法3: Floyd-WarshallComplexity There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

N will be in the range [1, 100].K will be in the range [1, N].The length of times will be in the range [1, 6000].All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

方法1: Dijkstra

思路：

模版Dijkstra。

Complexity

Time complexity: O(V log E + E log E) Space complexity: O(V + E)

class Solution { public: int networkDelayTime(vector<vector<int>>& times, int N, int K) { vector<int> dist(N, INT_MAX); unordered_map<int, unordered_map<int, int>> adj; dist[K - 1] = 0; for (auto a: times) { int u = a[0] - 1, v = a[1] - 1, w = a[2]; adj[u][v] = w; } auto cmp = [](pair<int, int> & a, pair<int, int> & b) { return a.first > b.first; }; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp); pq.push({0, K - 1}); while (!pq.empty()) { auto top = pq.top(); pq.pop(); int u = top.second; int d = top.first; for (auto p: adj[u]) { int v = p.first; int w = p.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } int result = *max_element(dist.begin(), dist.end()); return result == INT_MAX ? -1 : result; } };

方法2: Bellman-Ford

思路：

模版Bellman-Ford, negative weight, but not negative cycles. Detect negative cycle. from CLRS page 651

易错点

avoid INT_MAX + w overflow。 // Bellman-Ford class Solution { public: int networkDelayTime(vector<vector<int>>& times, int N, int K) { vector<int> dist(N, INT_MAX); dist[K - 1] = 0; for (int i = 1; i < N; i++) { for (auto a: times) { int u = a[0] - 1, v = a[1] - 1, w = a[2]; if (dist[u] != INT_MAX && dist[v] > dist[u] + w) { dist[v] = dist[u] + w; } } } int result = *max_element(dist.begin(), dist.end()); return result == INT_MAX ? -1 : result; } };

Complexity

Time complexity: O(VE) Space complexity: O(V)

方法3: Floyd-Warshall

思路：

模版Floyd-Warshall, all pair, negative weight, but not negative cycles.

Complexity

Time complexity: O(V^3) Space complexity: O(V^2)

// Floyd-Warshall class Solution { public: int networkDelayTime(vector<vector<int>>& times, int N, int K) { vector<vector<int>> dist(N, vector<int>(N, INT_MAX)); for (int i = 0; i < N; i++) dist[i][i] = 0; for (auto a: times) { int u = a[0] - 1, v = a[1] - 1, w = a[2]; dist[u][v] = w; } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } } int result = *max_element(dist[K - 1].begin(), dist[K - 1].end()); return result == INT_MAX ? -1 : result; } };