Find the City With the Smallest Number of Neighbors at a Threshold Distance

For a given bidirectional weighted graph, find the node (city) with the least number of nodes reachable within a given threshold.

Note: If there are multiple such nodes, then return the node with the highest value among them.

Time Complexity: O(n^3)

const findtheCity = (n, edges, threshold) => {
  const adjMatrix = Array(n);

  for (let i = 0; i < n; i++) {
    adjMatrix[i] = [];
    for (let j = 0; j < n; j++) {
      adjMatrix[i][j] = (i === j) ? 0 : Number.MAX_VALUE;
    }
  }

  for (const val of edges) {
    adjMatrix[val[0]][val[1]] = val[2];
    adjMatrix[val[1]][val[0]] = val[2];
  }

  fw(adjMatrix);

  let minNeighbours = Number.MAX_VALUE;
  let neighbour;
  for (let i = 0; i < n; i++) {
    let currNeighbours = 0;

    for (let j = 0; j < n; j++) {
      if (adjMatrix[i][j] <= threshold) {
        currNeighbours++;
      }
    }

    if (currNeighbours <= minNeighbours) {
      minNeighbours = currNeighbours;
      neighbour = i;
    }
  }

  return neighbour;
};


const fw = (adjMatrix) => {
  const n = adjMatrix.length;
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        adjMatrix[i][j] = Math.min(adjMatrix[i][j],
        adjMatrix[i][k] + adjMatrix[k][j]);
      }
    }

  }
};

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

Demo