Shortest Path via the Floyd-Marshall algorithm

find-city.js

/**************************************************************************************************************
 *                                                                                                            *
 * The Floyd-Marshall algorithm:                                                                              *
 * https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm                                             *
 *                                                                                                            *
 * This file presents a solution to this problem:                                                             *
 * https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/ *
 *                                                                                                            *
 **************************************************************************************************************/

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number} distanceThreshold
 * @return {number}
 */
const findTheCity = function(n, edges, distanceThreshold) {
    const m = matrix(n);
    applyEdges(edges, distanceThreshold, m);
    //console.log('initialState:\n', m);
    calculateShortestPaths(distanceThreshold, n, m);
    //console.log('shortestPaths:\n', m);
    return pickTheWinner(n, m);
};

/**
 * Starting-point matrix. 
 *
 * @param {number} n
 * @return {number[][]} Array of n*n elements
 * representing a disconnected graph.
 */
const matrix = (n) => {
    const out = Array(n);
    for (let i = 0; i < n; i++) {
        const row = Array(n).fill(Number.MAX_SAFE_INTEGER);
        row[i] = 0;
        out[i] = row;
    }
    return out;
}

/**
 * Update matrix `m` in-place with edges.
 * Note: edges are bidirectional
 *
 * @param {number[][]} edges (bidirectional)
 * @param {number} t distance threshold
 * @param {number[][]} m the matrix
 * @return undefined
 */
const applyEdges = (edges, t, m) => {
    edges.forEach((edge) => {
        m[edge[0]][edge[1]] = edge[2] <= t ? edge[2] : Number.MAX_SAFE_INTEGER;
        m[edge[1]][edge[0]] = edge[2] <= t ? edge[2] : Number.MAX_SAFE_INTEGER;
    });
}

/**
 * Apply Floyd-Warshall algorithm in-place to get
 * calculate shortest paths.
 *
 * https://www.youtube.com/watch?v=oNI0rf2P9gE
 *
 * @param {number} t distance threshold
 * @param {number} n # of cities
 * @param {number[][]} m the matrix
 * @return undefined
 */
const calculateShortestPaths = (t, n, m) => {
    for (let cityIdx = 0; cityIdx < n; cityIdx++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                //console.log('cityIdx', cityIdx, 'i:', i, 'j:', j);
                if (i === j) { continue; } // skip diagonals  
                if (i === cityIdx || j === cityIdx) { continue; } // skip row/col for cityIdx
                //console.log('m[i][j]:', m[i][j], 'm[i][cityIdx] + m[cityIdx][j]:', m[i][cityIdx] + m[cityIdx][j])
                const newDistance = Math.min(m[i][j], m[i][cityIdx] + m[cityIdx][j]);
                //console.log('newDistance:', newDistance, 't:', t);
                if (newDistance <= t) {
                    //console.log('newDistance <= t');
                    m[i][j] = newDistance; 
                }
            }
        }
    }
}

const pickTheWinner = (n, m) => {
    //console.log('picking the winner');
    let goal = n - 1;
    let winnerIdx = 0;
    m.forEach((row, i) => {
        const reachableCityCount = row.filter((d) => d !== 0 && d < Number.MAX_SAFE_INTEGER).length;
        //console.log('reachableCityCount:', reachableCityCount);
        if (reachableCityCount <= goal) {
            goal = reachableCityCount;
            winnerIdx = i;
            //console.log('new goal:', goal, 'new winnerIdx:', winnerIdx);
        }
    });
    return winnerIdx;
}

/////////////////////////////////////////////////////////////////////////////////

// Test 1

let n = 4;
let edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]];
let distanceThreshold = 4;
console.log('actual:', findTheCity(n, edges, distanceThreshold), 'expected: 3');

// Test 2

n = 5;
edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]];
distanceThreshold = 2;
console.log('actual:', findTheCity(n, edges, distanceThreshold), 'expected: 0');

// Test 3

n = 5;
edges = [[4,1,2],[0,4,8],[1,2,3],[1,0,2],[2,3,1],[3,0,1]];
distanceThreshold = 2;
console.log('actual:', findTheCity(n, edges, distanceThreshold), 'expected: 4');