Network Delay Time - CollegeStash

Calculate and return the network delay time if all “n” nodes in a network can be reached can be reached. If they cannot be reached return -1.

Input times -> [source, target, weight (time)]
n -> Number of nodes
k -> Source node

1<= k <= n <= 100

You can assume that there are no multi nodes.

The Bellman-Ford algorithm can be used to solve this.

Runtime: O(n^2)

const networkDelayTime = (times, n, k) => {
  const distFromSource = new Array(n + 1);  // Since, k >= 1.
  distFromSource.fill(Number.MAX_VALUE, 1);
  distFromSource[k] = 0;
  
  // (n - 1) Edges.
  for (let i = 0; i < n-1; i++) {
    for (const time of times) {
      if (distFromSource[time[0]] !== Number.MAX_VALUE && (distFromSource[time[0]] + time[2]) < distFromSource[time[1]]) {
        distFromSource[time[1]] = distFromSource[time[0]] + time[2];
      }
    }
  }
  
  const max = Math.max(...distFromSource.slice(1));
  return max === Number.MAX_VALUE ? -1 : max;
};

console.log(networkDelayTime([
  [2, 1, 1],
  [2, 3, 1],
  [3, 4, 1]
], 4, 2));
// 2

Demo

Related