Network Delay Time

Level - Medium

Statement

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 maximum 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

You can try it at

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

Example

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

Approach

• please before going to solution section it is utmost important to implement dijkstra algo, because it is almost same.
• just we need to change the create graph function because in this we need directed graph
• after getting shortest time from source node to all the other nodes, extract the maximum time we get.
• if any shortest time is infinite means source node can't able to reach at target node hence return -1.

Java

class Solution {
     // main function
    public int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S)
    {
        int[] dis = new int[V];// distance array
        // distance from a node from source to all other node is infinite for now and distance from S to S is 0
        for(int i=0;i<V;i++){
            if(S!=i)dis[i] = Integer.MAX_VALUE;
        }
        // Priority Queue to select the shortest distance first, min-heap-priority-queue
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);// consist of [node,dis]
        pq.add(new int[]{S,0});// add source node to S and dis to be 0 
        while(!pq.isEmpty()){
            int[] element = pq.poll();// poll the node
            int node = element[0],wt = element[1];
            // get all the neighbour of node
            ArrayList<ArrayList<Integer>> neighbours = adj.get(node);
            for (ArrayList<Integer> neigh : neighbours) {
                int neigh_node = neigh.get(0),dis_from_node = neigh.get(1);
                if(wt+dis_from_node < dis[neigh_node]){
                    dis[neigh_node] = wt+dis_from_node;// update the distance of neigh node
                    pq.add(new int[]{neigh_node,dis[neigh_node]});
                }
            }
        }
        return dis;
    }
    public ArrayList<ArrayList<ArrayList<Integer>>> createDirectedGraph(int V,int E,int[][] edges){
        ArrayList<ArrayList<ArrayList<Integer>>> adj = new ArrayList<>();
        // there are V nodes
        for(int i=0;i<V;i++){
            adj.add(new ArrayList<>());
        }
        // iterate through all the edges
        for(int i=0;i<E;i++){
            int[] edge = edges[i];
            int u = edge[0],v = edge[1],w = edge[2];
            adj.get(u).add(new ArrayList<>(Arrays.asList(v,w)));// connect u to v with weight w
        }
        return adj;
    }
    public int networkDelayTime(int[][] times, int n, int k) {
        int E = times.length;
        n = n+1;// take n as n+1 because it is 1 based indexing
        ArrayList<ArrayList<ArrayList<Integer>>> adj = createDirectedGraph(n,E,times);  
        int[] res = dijkstra(n, adj, k);
        int maxi = Integer.MIN_VALUE;
        for(int i=1;i<n;i++){
            // System.out.println(res[i]);
            if(res[i]==Integer.MAX_VALUE)return -1;// means we can't reach this node from source node
            maxi = Math.max(res[i],maxi);
        }
        return maxi;
    }
}

CPP

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

class Solution {
public:
    vector<int> dijkstra(int V, vector<vector<vector<int>>>& adj, int S) {
        vector<int> dis(V, INT_MAX); // distance array
        dis[S] = 0; // distance from a node to itself is 0

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, S}); // add source node to S and distance to be 0
        while (!pq.empty()) {
            int wt = pq.top().first;
            int node = pq.top().second;
            pq.pop();

            if (wt > dis[node])
                continue;

            for (auto neigh : adj[node]) {
                int neigh_node = neigh[0];
                int dis_from_node = neigh[1];
                if (wt + dis_from_node < dis[neigh_node]) {
                    dis[neigh_node] = wt + dis_from_node;
                    pq.push({dis[neigh_node], neigh_node});
                }
            }
        }

        return dis;
    }

    vector<vector<vector<int>>> createDirectedGraph(int V, int E, vector<vector<int>>& edges) {
        vector<vector<vector<int>>> adj(V);
        for (auto edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            adj[u].push_back({v, w}); // connect u to v with weight w
        }
        return adj;
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        int E = times.size();
        n = n + 1; // take n as n+1 because it is 1-based indexing
        vector<vector<vector<int>>> adj = createDirectedGraph(n, E, times);
        vector<int> res = dijkstra(n, adj, k);
        int maxi = INT_MIN;
        for (int i = 1; i < n; i++) {
            if (res[i] == INT_MAX)
                return -1; // means we can't reach this node from the source node
            maxi = max(res[i], maxi);
        }
        return maxi;
    }
};

Python

import heapq

class Solution:
    def dijkstra(self, V, adj, S):
        dis = [float('inf')] * V  # distance array
        dis[S] = 0  # distance from source to itself is 0

        pq = [(0, S)]  # priority queue to select the shortest distance first
        while pq:
            wt, node = heapq.heappop(pq)
            if wt > dis[node]:
                continue
            for neigh_node, dis_from_node in adj[node]:
                if wt + dis_from_node < dis[neigh_node]:
                    dis[neigh_node] = wt + dis_from_node
                    heapq.heappush(pq, (dis[neigh_node], neigh_node))

        return dis

    def createDirectedGraph(self, V, E, edges):
        adj = [[] for _ in range(V)]
        for edge in edges:
            u, v, w = edge
            adj[u].append((v, w))
        return adj

    def networkDelayTime(self, times, n, k):
        E = len(times)
        n = n + 1  # take n as n+1 because it is 1-based indexing
        adj = self.createDirectedGraph(n, E, times)
        res = self.dijkstra(n, adj, k)
        maxi = float('-inf')
        for i in range(1, n):
            if res[i] == float('inf'):
                return -1  # means we can't reach this node from the source node
            maxi = max(res[i], maxi)
        return maxi

Time Complexity

O(nlog(n) + E)