Network Delay Time

Link

Description

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

• Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
• Output: 2

Example 2:

• Input: times = [[1,2,1]], n = 2, k = 1
• Output: 1

Example 3:

• Input: times = [[1,2,1]], n = 2, k = 2
• Output: -1

Constraints:

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Solution

SPFA

class Solution {
private:
    static const int N = 110, M = 6010;
    int h[N], e[M], w[M], ne[M], idx;
    int dist[N];
    bool st[N];

    void add(int a, int b, int weight) {
        e[idx] = b, w[idx] = weight, ne[idx] = h[a], h[a] = idx++;
    }

    void SPFA(int start) {
        queue<int> q;
        q.push(start);
        dist[start] = 0;

        while (!q.empty()) {
            int t = q.front(); q.pop();
            st[t] = false;

            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i];
                    if (!st[j]) {
                        q.push(j); st[j] = true;
                    }
                }
            }
        }
    }

public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        memset(dist, 0x3f, sizeof(dist));
        memset(h, -1, sizeof(h));
        idx = 0;

        for (auto& edge: times) {
            int a = edge[0], b = edge[1], weight = edge[2];
            add(a, b, weight);
        }

        SPFA(k);

        int res = 1;
        for (int i = 1; i <= n; i++) res = max(res, dist[i]);
        if (res == 0x3f3f3f3f) res = -1;
        return res;
    }
};

Another way of writing:

#include <optional>

class Graph {
private:
    unordered_map<int, vector<pair<int, int>>> adjList;

public:
    void addEdge(int src, int dest, int weight) {
        adjList[src].emplace_back(dest, weight);
    }

    const vector<pair<int, int>>& getNeighbors(int node) const {
        return adjList.at(node);
    }

    bool hasNode(int node) const { 
        return adjList.find(node) != adjList.end();
    }
};

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        Graph graph;
        for (const auto& edge: times) {
            graph.addEdge(edge[0], edge[1], edge[2]);
        }

        vector<optional<int>> dist(n + 1, nullopt);
        dist[k] = 0;
        queue<int> q;
        q.push(k);

        while (!q.empty()) {
            int node = q.front(); q.pop();

            if (!graph.hasNode(node)) continue;

            for (const auto& [neighbor, weight] : graph.getNeighbors(node)) {
                int newDist = *dist[node] + weight;
                if (!dist[neighbor] || newDist < *dist[neighbor]) {
                    dist[neighbor] = newDist;
                    q.push(neighbor);
                }
            }
        }

        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (!dist[i]) return -1;
            maxTime = max(maxTime, *dist[i]);
        }
        return maxTime;
    }
};

This code uses std::optional. The code encapsulates the graph's adjacency list representation. It uses an unordered map from nodes to a vector of pairs, representing edges and their weights.

Time Complexity Analysis:

1. Graph Construction: For each edge in the times vector, we add an entry to the adjacency list. Since there are E edges in the times vector, this operation takes \(O(E)\) time.
2. SPFA Algorithm: The Shortest Path Faster Algorithm, in the worst case, can have a time complexity similar to that of the Bellman-Ford algorithm, which is \(O(VE)\) for a graph with \(V\) vertices and \(E\) edges. However, SPFA performs better in practice on average, often closer to \(O(E)\). This is because, unlike Bellman-Ford, SPFA does not process every edge in every iteration; it only processes edges connected to nodes that have been relaxed in the previous iteration.
3. Worst-Case Scenario: In the worst case, where the graph might have a negative weight cycle (not applicable in this context as times are positive), SPFA's time complexity can approach \(O(VE)\).
4. Average Case: In practice, especially with non-negative edge weights, the complexity is often much better and can be approximated to \(O(E)\) for most scenarios.
5. Finding Maximum Time: After running SPFA, we iterate over the dist array to find the maximum time. This is \(O(V)\) as we go through each of the \(V\) vertices.

Combining these, the average case time complexity of the algorithm is \(O(E + V)\), where \(E\) is the number of edges and \(V\) is the number of vertices. In the worst case, it could be \(O(VE + V)\) due to the nature of SPFA.

Space Complexity Analysis:

1. Graph Representation: We use an adjacency list to represent the graph. In the worst case, if the graph is dense, this can take \(O(V + E)\) space, accounting for all vertices and edges.
2. Distance Vector: The dist vector is of size \(V\) (number of vertices), so it takes \(O(V)\) space.
3. Queue in SPFA: In the worst case, the queue can have all vertices, taking \(O(V)\) space.

Therefore, the total space complexity of the algorithm is \(O(V + E)\), which is required for storing the graph and auxiliary data structures used in SPFA.