> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/743.-network-delay-time.md).

# 743. Network Delay Time

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`.

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png)

```
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2
```

**Note:**

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

```cpp
// Floyd–Warshall Algorithm
int networkDelayTime(vector<vector<int>>& times, int N, int K) { // time: O(V^3); space: O(V^2)
    vector<vector<double> > dist(N + 1, vector<double>(N + 1, numeric_limits<int>::max()));
    for (int i = 1; i <= N; ++i) dist[i][i] = 0;
    for (const vector<int>& t : times) dist[t[0]][t[1]] = t[2];
    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    double res = 0;
    for (int i = 1; i <= N; ++i) {
        if (dist[K][i] == numeric_limits<int>::max()) return -1;
        res = max(res, dist[K][i]);
    }
    return (int)res;
}
```

```cpp
// Bellman-Ford Algortihm
int networkDelayTime(vector<vector<int>>& times, int N, int K) { // time: O(V * E); space: O(V)
    vector<int> dist(N + 1, numeric_limits<int>::max());
    dist[K] = 0;
    // Do N - 1 times relaxation
    for (int i = 1; i < N; ++i) {
        for (auto& t : times) {
            int u = t[0], v = t[1], w = t[2];
            // relaxation
            if (dist[u] != numeric_limits<int>::max() && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
            }
        }
    }
    // int res = 0;
    // for (int i = 1; i <= N; ++i) {
    //     res = max(res, dist[i]);
    // }
    int res = *max_element(dist.begin() + 1, dist.end());
    return res == numeric_limits<int>::max() ? -1 : res;
}
```

```cpp
// Bellman-Ford Algortihm
int networkDelayTime(vector<vector<int>>& times, int N, int K) { // time: O(V * E); space: O(V)
    vector<vector<pair<int, int> > > graph(N + 1); // adjacency list
    for (const vector<int>& t : times) graph[t[0]].push_back({t[1], t[2]});
    vector<int> dist(N + 1, numeric_limits<int>::max());
    dist[K] = 0;
    // vector<bool> visited(N + 1, false);
    queue<int> q({K});
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (const pair<int, int>& g : graph[u]) {
            int v = g.first, w = g.second;
            if (dist[u] != numeric_limits<int>::max() && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push(v);
            }
        }
    }
    int res = *max_element(dist.begin() + 1, dist.end());
    return res == numeric_limits<int>::max() ? -1 : res;
}
```

```cpp
// Dijkstra Algorithm
int networkDelayTime(vector<vector<int>>& times, int N, int K) { // time: O(V^2); space: O(V^2)
    // Adjacency matrix
    vector<vector<int> > edges(N + 1, vector<int>(N + 1, -1) );
    for (auto t : times) edges[t[0]][t[1]] = t[2];
    vector<int> dist(N + 1, numeric_limits<int>::max());
    dist[K] = 0;
    queue<int> q({K});
    while (!q.empty()) {
        for (int k = q.size() - 1; k >= 0; --k) {
            int u = q.front(); q.pop();
            for (int v = 1; v <= N; ++v) {
                if (edges[u][v] != -1 && dist[u] != numeric_limits<int>::max() && dist[v] > dist[u] + edges[u][v]) {
                    q.push(v);
                    dist[v] = dist[u] + edges[u][v];
                }
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= N; ++i) {
        res = max(res, dist[i]);
    }
    return res == numeric_limits<int>::max() ? -1 : res;
}
```

```cpp
// Dijkstra Algorithm
int networkDelayTime(vector<vector<int>>& times, int N, int K) { // time: O(E + E * log(V)); space: O(V + E)
    vector<vector<pair<int, int> > > graph(N + 1); // Adjacency list
    for (const vector<int>& t : times) graph[t[0]].push_back({t[1], t[2]}); // O(E)
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    pq.push({0, K});
    vector<int> dist(N + 1, numeric_limits<int>::max());
    dist[K] = 0;
    vector<bool> visited(N + 1, false);
    // At most, E times push operations will be conducted to push vertex into pq
    while (!pq.empty()) {
        pair<int, int> t = pq.top(); pq.pop();
        int u = t.second;
        if (visited[u]) continue;
        visited[u] = true;
        for (const pair<int, int>& edge : graph[u]) {
            int v = edge.first, w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    int res = *max_element(dist.begin() + 1, dist.end()); // dist.begin() is not used
    return res == numeric_limits<int>::max() ? -1 : res;
}
```