Shortest path in a graph
Francisco Becker
8806
Graph TheoryShortest Path

Hello fellow Leetcoders, I've been recently studying graphs, and I came upon this BFS example of how to find the path from a root node to all other nodes in a graph.
The path is the amount of hops needed to get to a given node.
I've searched Leetcode for a similar problem, and I was not able to find it.
If anyone knows of a similar problem in Leetcode, please share it in the comments below. Also share any good graph resources you might have for folks trying to get better at Graph problems. Thank you!!

Here is the problem and solution below:

const graph =
  [//A  B  C  D  E  F  G  H  I
    [0, 1, 1, 1, 0, 0, 0, 0, 0], //A
    [1, 0, 0, 0, 1, 1, 0, 0, 0], //B
    [1, 0, 0, 1, 0, 0, 1, 0, 0], //C
    [1, 0, 1, 0, 0, 0, 1, 1, 0], //D
    [0, 1, 0, 0, 0, 0, 0, 0, 1], //E
    [0, 1, 0, 0, 0, 0, 0, 0, 0], //F
    [0, 0, 1, 1, 0, 0, 0, 0, 0], //G
    [0, 0, 0, 1, 0, 0, 0, 0, 0], //H
    [0, 0, 0, 0, 1, 0, 0, 0, 0], //I
  ]

function bfs(v) { // v is the origin
  const queue = [v], d = {}, pred = {}

  for (let i = 0; i < graph.length; i++) {
    d[i] = Infinity;
  }
  // set the root distance
  d[v] = 0
  while (queue.length) {
    const u = queue.shift()
    const neighbors = graph[u]
    for (let i = 0; i < neighbors.length; i++) {
      const n = neighbors[i]
      if (!n) continue
      if (d[i] == Infinity) {
        d[i] = (d[u] || 0) + 1
        pred[i] = u
        queue.push(i)
      }
    }
  }
  return { distances: d, predecessors: pred }
}
console.log(bfs(0)) // pass in the origin node
Comments (2)