Breadth First Search algorithm

// Breadth First Search implementation in purest form

// relationship between nodes
const graph5 = [
  [1, 2], // SFO, index 0
  [0, 2, 3], // ORD, index 1
  [0, 1, 3, 4], // DEN, index 2
  [1, 2, 4], // JFK, index 3
  [2, 3], // IAH, index 4
]

// nodes' information
const idxToAirport = {
  '0': { name: 'SFO' },
  '1': { name: 'ORD' },
  '2': { name: 'DEN' },
  '3': { name: 'JFK' },
  '4': { name: 'IAH' }
}

const breadthFirstSearchPure = (initNodeIdx) => {
  const result = []
  const seen = new Set()
  const queue = [initNodeIdx] // REMEMBER to use a proper queue data structure IRL

  console.log('Starting airport: ', idxToAirport[initNodeIdx].name)

  while(queue.length > 0) {

    const curNodeIdx = queue.shift() // dequeue

    // if we've never seen this node before, process,
    // otherwise, ignore the node
    if(!seen.has(curNodeIdx)) {

      seen.add(curNodeIdx) // add this node to seen list

      const curNodeNeighbors = graph5[curNodeIdx] // get the neighbors
      curNodeNeighbors.forEach(nodeIdx =>
        !seen.has(nodeIdx) && queue.push(nodeIdx)) // enqueue neighbors
  
      result.push(idxToAirport[curNodeIdx].name) // save current node to result

      console.log('result: ', result)
    }
  }
}

breadthFirstSearchPure(0) // result: [ 'SFO', 'ORD', 'DEN', 'JFK', 'IAH' ]

$ node breadth-first-search-pure.js
Starting airport:  SFO
result:  [ 'SFO' ]
result:  [ 'SFO', 'ORD' ]
result:  [ 'SFO', 'ORD', 'DEN' ]
result:  [ 'SFO', 'ORD', 'DEN', 'JFK' ]
result:  [ 'SFO', 'ORD', 'DEN', 'JFK', 'IAH' ]

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

var networkDelayTime = function(times, n, k) {

  // initialize graph with empty arrays
  const graph = []
  for(let i = 0; i < n; i++) { graph.push([]) }
  console.log('graph:', graph)

  // build adjacency list graph with `times` data
  for(let i = 0; i < times.length; i++) {
    const nodeIdx = times[i][0] - 1
    const neighborIdx = times[i][1] - 1
    const travelTime = times[i][2]
    graph[nodeIdx].push([neighborIdx, travelTime])
  }
  console.log('graph:', graph)
  

  const initNodeIdx = k - 1 // our graph is 0-indexed from given 1-indexed data
  const layerEnd = '|' // layer separator in the queue
  const queue = [initNodeIdx, layerEnd] // initialize the queue
  const seen = new Set([initNodeIdx]) // keep track of seen nodes
  let paths = [[0, initNodeIdx]] // the first num (0) is total travel time
  

  while(queue.length > 0) {
    // console.log('queue: ', queue)

    const curNodeIdx = queue.shift() // dequeue

    // add layer separator `|` whenever a layer finishes
    if(curNodeIdx === layerEnd && queue.length > 0) {
      queue.push(layerEnd)
      continue
    }

    // break out of the loop when there's no data left in the queue
    if(curNodeIdx === layerEnd && queue.length === 0) {
      break
    }

    const curNode = graph[curNodeIdx] // get current node neighbors
    const tempPaths = [] // update paths

    // for every neighbor
    for(let i = 0; i < curNode.length; i++) {
      const [neighborNodeIdx, neighborTravelTime] = curNode[i]

      // if this neighbor hasn't been seen
      if(!seen.has(neighborNodeIdx)) {
        seen.add(neighborNodeIdx) // add to seen list
        queue.push(neighborNodeIdx) // add to the queue

        // update path with this new neighor + travel time to this neighbor
        for(let j = 0; j < paths.length; j++) {
          if (paths[j][paths[j].length - 1] === curNodeIdx) {
            const updatePath = paths[j].concat(neighborNodeIdx)
            updatePath[0] += neighborTravelTime
            tempPaths.push(updatePath)
          } else {
            tempPaths.push(paths[j])
          }
        }
      }
    }
    
    tempPaths.length !== 0 && (paths = tempPaths)
    console.log('paths: ', paths)
  }

  // if we don't see all the nodes -> can't reach to every node -> return -1
  if(seen.size !== n) {
    return -1
  } else {
    let max = 0
    for(let i = 0; i < paths.length; i++) {
      if(paths[i][0] > max) max = paths[i][0]
    }
    return max
  }
}

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

$ node network-delay-time.js
graph: [ [], [], [], [] ]
graph: [ [], [ [ 0, 1 ], [ 2, 1 ] ], [ [ 3, 1 ] ], [] ]
paths:  [ [ 1, 1, 0 ], [ 1, 1, 2 ] ]
paths:  [ [ 1, 1, 0 ], [ 1, 1, 2 ] ]
paths:  [ [ 1, 1, 0 ], [ 2, 1, 2, 3 ] ]
paths:  [ [ 1, 1, 0 ], [ 2, 1, 2, 3 ] ]
2

// BFS shortest path on matrix

const shortestPath = (map, start, end) => {
  
  matprint(map)
  console.log('starting position:', start)
  console.log('target position:', end)

  const queue = [start]
  const seen = new Set()
  let paths = [['' + start[0] + start[1]]] // initial start at `00`, [['00']]

  while(queue.length > 0) {

    console.log('queue:', queue)
    // console.log('paths:', paths)

    const [row, col] = queue.shift() // dequeue

    console.log('current node (row, col):', row, col)

    const strRowCol = '' + row + col // `00` etc.

    if(!seen.has(strRowCol)) { // if we've never seen this node before, process

      seen.add(strRowCol) // mark this node as seen
      
      const tempPaths = [] // path + new neighbor node will be temp saved here
      const seenNoNewNeiboPaths = new Set() // keep track of path has no new neighbor

      // list of 4 neighbors' indexes: left, right, up, down
      const neighborIdxes = [[row+1, col], [row-1, col], [row, col+1], [row, col-1]]

      // for each neighbor
      for(let i = 0; i < neighborIdxes.length; i++) {

        const [neighborRow, neighborCol] = neighborIdxes[i]
        const strNeighborRowCol = '' + neighborRow + neighborCol // `01` etc.

        if(
          (neighborRow < 8) && // if neighbor index is not out of
          (neighborRow > -1) && // matrix (0 <= index <= 7)
          (neighborCol < 8) &&
          (neighborCol > -1) &&
          map[neighborRow][neighborCol] !== 1 && // and movable to this neighbor
          !seen.has(strNeighborRowCol) // and we've never seen that neighbor before
        ) {

          queue.push([neighborRow, neighborCol]) // enqueue neighbor node

          // update path with this neighor. AKA paths [[00]] -> paths [[00, 01]]
          for(let j = 0; j < paths.length; j++) {

            if (paths[j][paths[j].length - 1] === strRowCol) { // continue path
              const updatePath = paths[j].concat(strNeighborRowCol)
              tempPaths.push(updatePath)

              if(strNeighborRowCol === '77') { // first path reaches target
                matprint(map, updatePath)
                return updatePath // return this path and exit
              }
            } else { // only save to temp path once, path with no new neighbor
              !seenNoNewNeiboPaths.has(paths[j][paths[j].length - 1]) &&
                tempPaths.push(paths[j])
              seenNoNewNeiboPaths.add(paths[j][paths[j].length - 1])
            }
          }
         
        }
      }

      // update paths with tempPaths
      tempPaths.length !== 0 && (paths = tempPaths)
    }

    console.log('======================= new queue item ====')
  }

  // console.log('paths: ', paths)

  // for(let i = 0; i < paths.length; i++) {
  //   matprint(map, paths[i])
  //   console.log('=====================================')
  // }
}

const map = [
  [0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 1, 1, 0, 0],
  [0, 0, 0, 0, 0, 1, 0, 1],
  [0, 1, 1, 1, 0, 1, 0, 0],
  [0, 0, 0, 0, 0, 1, 0, 1],
  [0, 1, 1, 1, 1, 1, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
]

console.log(shortestPath(map, [0,0], [7,7]))




/**
 * Pretty print a matrix helper function
 * https://gist.github.com/lbn/3d6963731261f76330af
 * @param {*} mat 
 */
function matprint(mat, path = []) {
  let shape = [mat.length, mat[0].length];
  function col(mat, i) {
      return mat.map(row => row[i]);
  }
  let colMaxes = [];
  for (let i = 0; i < shape[1]; i++) {
      colMaxes.push(Math.max.apply(null, col(mat, i).map(n => n.toString().length)));
  }

  mat.forEach((row, rowIdx) => {
    console.log.apply(null, row.map((val, j) => {
      if (val === 0) val = '-';
      if(path.length != 0) {
        if(path.includes('' + rowIdx + j)) val = '*'
      }
      if (rowIdx === 0 && j == 0) val = 'S';
      if (rowIdx === 7 && j == 7) val = '⭐';
      return new Array(colMaxes[j]-val.toString().length+1).join(" ") + val.toString() + "  ";
    }));
  });
}

$ node shortest-path-matrix.js
S   -   -   -   1   -   1   -  
1   -   1   -   -   -   -   -  
-   -   -   1   1   1   -   -  
-   -   -   -   -   1   -   1  
-   1   1   1   -   1   -   -  
-   -   -   -   -   1   -   1  
-   1   1   1   1   1   -   -  
-   -   -   -   -   -   -   ⭐  
starting position: [ 0, 0 ]
target position: [ 7, 7 ]
queue: [ [ 0, 0 ] ]
current node (row, col): 0 0
======================= new queue item ====
queue: [ [ 0, 1 ] ]
current node (row, col): 0 1

...

======================= new queue item ====
queue: [ [ 7, 6 ], [ 6, 7 ], [ 7, 5 ] ]
current node (row, col): 7 6
S   *   *   *   1   -   1   -  
1   -   1   *   *   *   *   -  
-   -   -   1   1   1   *   -  
-   -   -   -   -   1   *   1  
-   1   1   1   -   1   *   -  
-   -   -   -   -   1   *   1  
-   1   1   1   1   1   *   -  
-   -   -   -   -   -   *   ⭐  
[
  '00', '01', '02', '03',
  '13', '14', '15', '16',
  '26', '36', '46', '56',
  '66', '76', '77'
]