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:

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.

// 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;
}

// 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;
}

// 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;
}

// 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;
}

// 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;
}