743. Network Delay Time

• Link: https://leetcode.com/problems/network-delay-time

Question

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

Approach 1: Dijkstra's Algorithm

Intuition

• Shortest path with weighted edges and without negative weights

Algorithm

1. Convert from edge list to adj list
2. Initialize a Priority Queue with type pair<int, int> and a distance array with INT_MAX
3. Push the source node into the priority queue with distance 0
4. Loop till pq is not empty
   1. Get the top node and its curr distance
   2. Pop the pq
   3. Loop over the adj list for the neighbors of the current node
      1. Calculate new distance
      2. Check if the new distance is less than the existing distance in the distance array
         1. Push the node and the new distance into the pq
         2. Update the distance array to the new distance
5. Declare and initialize a maxTime variable with INT_MIN (to calculate the max time the distance array requires)
6. Loop over the distance array
   1. If any distance is INT_MAX (i.e; not updated / not reachable) return -1;
   2. Update the maxTime to the max of the current distance and maxTime.
7. Return maxTime.

Code

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // 0. Coverting edge list to adj list
        // n + 1 -> because question suggests 1 to n nodes
        vector<vector<vector<int>>> adj(n + 1, vector<vector<int>>());

        for (auto& edge: times) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];

            adj[u].push_back({v, w});
            adj[u].push_back({v, w});
        }

        // 1. Dijkstra's algorithm
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        pq.push({k, 0});
        vector<int> dist(n + 1, INT_MAX);
        dist[k] = 0;

        while(!pq.empty()) {
            int node = pq.top().first;
            int currDist = pq.top().second;
            pq.pop();

            for (auto& it: adj[node]) {
                int neighbor = it[0];
                int weight = it[1];
                int newWeight = weight + currDist;

                if (newWeight < dist[neighbor]) {
                    dist[neighbor] = newWeight;
                    pq.push({neighbor, newWeight});
                }
            }
        }

        int maxTime  = INT_MIN;
        for (int i = 1 ; i < n + 1 ; i++) {
            if (dist[i] == INT_MAX) {
                return -1;
            }

            maxTime = max(dist[i], maxTime);
        }

        return maxTime;
    }
};

Complexity Analysis

• Time Complexity: $O((V+E)\log V)$
• Space Complexity: $O(V+E)$