Returning the shortest path using breadth first search

#javascript #breadthfirstsearch #graphs

In a previous post, I walked through how to use breadth first search to find whether a node was in a binary tree. In this post, I'm going to discuss how to get the list for the shortest path connecting two nodes using breadth first search.

Let's say you had a tree, such as the following:

If you wanted a list of what the shortest path connecting 1 and 10 would be, you could tell just by looking at the tree that the list would be [1, 3, 7, 10]. Doing this algorithmically, however, takes a bit of work.

Just as I discussed in a previous post, with BFS you'll want to implement a queue--first in, first out--to check nodes. With BFS, you check all of the children of a node, and then those children's children, until you find what you're looking for.

Another important thing to keep in mind is that you don't want to go back to the same node and recheck it multiple times. To avoid doing this, you have to keep track of which nodes you've already seen.

One way to approach this problem is to create an adjacency list. An adjacency list is an object that stores the neighbors of the nodes in a graph. You can learn more about building adjacency lists here.

An adjacency list of the above graph would look like the following:

adjacencyList = {
        '1': [2, 3],
        '2': [4, 5],
        '5': [8, 9],
        '3': [6, 7],
        '7': [10]
        }

Now we can build a function that searches through this graph, using the adjacency list. We'll start by declaring the function, which takes in the adjacency list, the start node, and the end node.

function shortestPath(graph, start, end) {
  //...

}

First we will initialize a queue, which will be the value at the start node.

function shortestPath(graph, start, end) {
  let queue = [[start]]
  //...

}

Then, in order to keep track of which nodes we've already visited, we'll initialize a set.

function shortestPath(graph, start, end) {
  let queue = [[start]]
  let visitedNodes = new Set()
  //...

}

Now, as long as there are items in the queue, we'll check the first element.

function shortestPath(graph, start, end) {
  let queue = [[start]]
  let visitedNodes = new Set()
  while (queue.length > 0) {
    let path = queue.shift()
    //...
  }
}

Now, path is the first path that's in the queue. We want to check the last item in that path. If that last item is the end goal, then we can return the path.

function shortestPath(graph, start, end) {
  let queue = [[start]]
  let visitedNodes = new Set()
  while (queue.length > 0) {
    let path = queue.shift()
    let currentNode = path[path.length - 1]
    if (currentNode === end) {
      return path
    }
    //...
  }
}

Otherwise, we need to check if currentNode has already been checked.

function shortestPath(graph, start, end) {
  let queue = [[start]]
  let visitedNodes = new Set()
  while (queue.length > 0) {
    let path = queue.shift()
    let currentNode = path[path.length - 1]
    if (currentNode === end) {
      return path
    } else if (!visitedNodes.has(currentNode)) {
      //...
      }
  }
}

If the current node hasn't yet been checked, then we will get the neighbor nodes based on the adjacency list, and make a new path from those. We'll push that new path to the back of the queue. We also will add the currentNode to the visitedNodes set.

function shortestPath(graph, start, end) {
  let queue = [[start]]
  let visitedNodes = new Set()
  while (queue.length > 0) {
    let path = queue.shift()
    let currentNode = path[path.length - 1]
    if (currentNode === end) {
      return path
    } else if (!visitedNodes.has(currentNode)) {
      let neighborNodes = graph[currentNode]
      queue.append(neighborNodes)
      visitedNodes.add(currentNode)
    }
  }
}

And that's it! This function should search through an adjacency list, checking the values, avoiding duplicates, and return the shortest path between two nodes.