Leetcode 743. Network Delay Time

Problem Explanation

The problem involves a network of nodes, with edges that represent the time it takes for a signal to travel from one node to another. Each edge is directed, meaning the signal can only travel in the specified direction. Given this network, a signal is sent from a certain node, and the task is to find out how long it will take for all the nodes to receive the signal. If it is impossible for a node to receive the signal due to the direction of the edges, the problem asks us to return -1.

For example, consider the following network where N=4 and K=2, meaning we have 4 nodes and we're starting at node 2. The time it takes for a signal to travel between nodes is given in the array times:

times = [[2,1,1],[2,3,1],[3,4,1]]

This translates to:

• Signal can travel from 2 to 1 in a time of 1
• Signal can travel from 2 to 3 in a time of 1
• Signal can travel from 3 to 4 in a time of 1

Starting from node 2, the time taken for all nodes to receive the signal will be 2, because the signal travels from 2->3 and then from 3->4, taking 1 time unit each for a total of 2 time units.

Solution Approach

The solution uses Dijkstra's algorithm, which is a shortest path algorithm for a graph. It uses a priority queue to select the closest node to the source and determines the shortest path to all nodes from the source. If a node cannot be reached, it will remain marked as an infinite distance.

Walking through Dijkstra's algorithm with the same example as before, the steps would be as follows:

• Initialize a distance array with maximum integer value (representing infinite distance) for all nodes, and set the distance to the source node (2 in this case) to 0
• Insert the source node into a priority queue
• While the queue isn't empty, remove the node (let's call this node u) with the shortest distance and update the distances to all its adjacent nodes (v). If the current distance to v is greater than the distance to u plus the weight of the edge connecting u and v, update the distance to v and insert it to the queue
• After the queue is empty, which means all reachable nodes have been explored, find the maximum distance in the distance array. If there's still a node with infinite distance, return -1 because this node can't be reached, otherwise return the maximum distance.

Python Solution

1
2python
3import heapq
4from collections import defaultdict
5
6class Solution(object):
7    def networkDelayTime(self, times, N, K):
8        # build the graph
9        graph = defaultdict(list)
10        for u, v, w in times:
11            graph[u].append((v, w))
12
13        # priority queue
14        pq = [(0, K)]
15        dist = {}
16        
17        while pq:
18            d, v = heapq.heappop(pq)
19            # check if v is visited 
20            if v in dist: continue
21                
22            dist[v] = d
23            for w, t in graph[v]:
24                if w not in dist:
25                    # add new unvisited vertex in priority queue 
26                    heapq.heappush(pq, (d + t, w))
27        
28        # return -1 if any vertex is not visited
29        if len(dist) != N: return -1
30
31        return max(dist.values())

Java Solution

1
2java
3class Solution {
4    public int networkDelayTime(int[][] times, int N, int K) {
5        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
6        for (int[] edge: times) {
7            graph.computeIfAbsent(edge[0], x->new HashMap<>()).put(edge[1], edge[2]);
8        }
9
10        PriorityQueue<int[]> heap = new PriorityQueue<>((info1, info2) -> info1[0] - info2[0]);
11        heap.offer(new int[]{0, K});
12        boolean[] visited = new boolean[N+1];
13
14        int ans = 0;
15        while (!heap.isEmpty()) {
16            int[] info = heap.poll();
17            int d = info[0], v = info[1];
18            if (visited[v]) continue;
19            visited[v] = true;
20            ans = d;
21            if (!graph.containsKey(v)) continue;
22            for (int w: graph.get(v).keySet()) {
23                if (!visited[w]) heap.offer(new int[]{d + graph.get(v).get(w), w});
24            }
25        }
26
27        for (int visitedNode: visited) {
28            if (!visitedNode) return -1;
29        }
30        return ans;
31    }
32}

JavaScript Solution

1
2javascript
3class Solution {
4    networkDelayTime(times, N, K) {
5        let graph = Array(N).fill(null).map(r => Array(N).fill(Infinity));
6        times.forEach(([start, end, time]) => graph[start - 1][end - 1] = time);
7        for (let i = 0; i < N; i++) {
8            graph[i][i] = 0;
9        }
10        
11        for (let k = 0; k < N; k++) {
12            for (let i = 0; i < N; i++) {
13                for (let j = 0; j < N; j++) {
14                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
15                }
16            }
17        }
18        
19        let max = Math.max(...graph[K - 1]);
20        return max === Infinity ? -1 : max;
21    }
22}

C++ Solution

1
2c++
3class Solution {
4public:
5    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
6        vector<vector<pair<int, int>>> graph(N);
7        for (const vector<int>& time : times) {
8            int u = time[0] - 1;
9            int v = time[1] - 1;
10            int w = time[2];
11            graph[u].emplace_back(v, w);
12        }
13        return dijkstra(graph, K - 1);
14    }
15
16private:
17    int dijkstra(const vector<vector<pair<int, int>>>& graph, int src) {
18        vector<int> dist(graph.size(), INT_MAX);
19        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
20        dist[src] = 0;
21        minHeap.emplace(dist[src], src);
22        while (!minHeap.empty()) {
23            const auto [d, u] = minHeap.top();
24            minHeap.pop();
25            for (const auto& [v, w] : graph[u])
26                if (d + w < dist[v]) {
27                    dist[v] = d + w;
28                    minHeap.emplace(dist[v], v);
29                }
30        }
31        const int maxDist = *max_element(begin(dist), end(dist));
32        return maxDist == INT_MAX ? -1 : maxDist;
33    }
34};

C# Solution

1
2csharp
3public class Solution {
4    public int NetworkDelayTime(int[][] times, int N, int K) {
5        int[,] dp = new int[N, N];
6        for(int i = 0; i < N; i++) {
7            for(int j = 0; j < N; j++) {
8                dp[i, j] = i == j ? 0 : Int32.MaxValue;
9            }
10        }
11        foreach(int[] edge in times) {
12            dp[edge[0]-1, edge[1]-1] = edge[2];
13        }
14        
15        for(int k = 0; k < N; k++) {
16            for(int i = 0; i < N; i++) {
17                for(int j = 0; j < N; j++) {
18                    if(dp[i, k] != Int32.MaxValue && dp[k, j] != Int32.MaxValue) dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j]);
19                }
20            }
21        }
22        int res = dp[K-1, 0];
23        for(int i = 1; i < N; i++) {
24            if(dp[K-1, i] == Int32.MaxValue) return -1;
25            res = Math.Max(res, dp[K-1, i]);
26        }
27        return res;
28    }
29}

The solution is designed to use Dijkstra's algorithm, a classic algorithm for finding the shortest paths from a source node to all other nodes in a weighted graph. Dijkstra's algorithm uses a priority queue to process nodes in order of distance from the source node. The heart of the algorithm is a relaxation process that improves the current distance estimate for a target node based on newly examined edges' weights.

The provided Python implementation creates a priority queue and a distance dictionary. For each edge in the network, it updates the distance dictionary to store the shortest confirmed distance from the source node to each reachable node. Once no more reachable nodes are left to explore, the function checks whether all nodes in the network were reachable, by comparing the size of the distance dict with the total number of nodes. If any unvisited node is found, the function returns -1.

The C++ version use a similar approach. In addition to a distance vector, it also maintains a priority queue. This implementation uses a nested loop inside the Dijkstra's algorithm loop for doing the relaxation process. The JavaScript implementation creates an adjacency matrix for the input network. It then employs the Floyd-Warshall algorithm, filling in the shortest paths between all pairs of nodes. After that, it fetches the longest shortest path for the starting node.

The C# solution approach is similar to the JavaScript implementation. It uses the Floyd-Warshall algorithm and populates the dp matrix with the shortest path information between all pairs. Then it queries the longest path starting from node K.

The Java implementation does the same as python implementation. It uses PriorityQueue as the min-heap to get the node with the shortest distance first. A boolean array is used to check if a node has been visited or not.

Each of these solutions demonstrates how Dijkstra's algorithm can be used to solve the network delay problem in different ways, using the features of different programming languages. For real-world application, the choice of implementation would depend on the specific requirements and constraints of the problem at hand.