A network of n nodes labeled 1 to n is provided along with a list of travel times for directed edges represented as times[i]=(x i ​ ​, y i ​ , t i ​ ​) , where x i ​ ​ is the source node, y i ​ ​ is the target node, and t i ​ ​ is the delay time from the source node to the target node. Considering we have a starting node, k, we have to determine…

network-delay-time.js

function networkDelayTime(times, n, k) {
  // times[i] = (xi, yi, ti)
  // k - starting node
  // n = total nodes
  // so we need an adj list 
  // a priority queue
  // a visited set
  // and a result variable

  // build an adjacency list from the times array
  // keys are nodes, values are arrays of tuples indicating outgoing edges, 
  // each tuple is a pair of [node, time]
  const list = times.reduce((acc, [vFrom, vTo, time]) => {
    if (!acc[vFrom]) {
      acc[vFrom] = [];
    }
    acc[vFrom].push([vTo, time]);
    return acc;
  }, {});

  // initialize pq with [node, time] where node is starting node and time is 0
  const pq = [[k, 0]];

  // keep visited nodes in a set
  const visited = new Set();

  let result = 0;

  // now the dijkstra algorithm
  // we are going to pop a tuple with the min time (min heap rule)
  // we are going to push all directly connected nodes of the popped node into pq with the times
  // which means we're going to visit all shortest connections first

  while (pq.length > 0) {
    // we imitate the min heap by sorting the array every time
    pq.sort(([v1, t1], [v2, t2]) => t2 - t1);
    const [v, t] = pq.pop();
    if (!visited.has(v)) {
      visited.add(v);
      result = Math.max(result, t);
      if (list[v]) {
        // add a node to the priority queue
        // node time is not just the time of the edge itself (from v to vc)
        // it's time of the edge itself + current result time
        pq.push(...(list[v].map(([vc, tc]) => ([vc, result + tc]))));
      }
    }
  }

  // if we haven't visited all the nodes, it means there is no solution, some nodes don't have incoming edges
  if (visited.size !== n) {
    return -1;
  }

  return result;
}

export { networkDelayTime };


// tc: 
// E = V^2 (maxiumum number of edges roughly equals to number of nodes squared)
// so max size of min heap is roughly V^2 (we add some nodes multiple times)
// heap operation complexity is logN
// so in this case it's logV^2
// we add values to the heap on each edge, so ElogV^2, that becomes 2ElogV => ElogV
// sc: O(E + V) space required is big O of sum of the number of edges and the number of vertices