DEV Community

Alisa Bajramovic
Alisa Bajramovic

Posted on

Returning the shortest path using breadth first search

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:
Tree to do breadth first search on

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]
        }


Enter fullscreen mode Exit fullscreen mode

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) {
  //...

}


Enter fullscreen mode Exit fullscreen mode

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



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

}


Enter fullscreen mode Exit fullscreen mode

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()
  //...

}


Enter fullscreen mode Exit fullscreen mode

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()
    //...
  }
}


Enter fullscreen mode Exit fullscreen mode

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
    }
    //...
  }
}


Enter fullscreen mode Exit fullscreen mode

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)) {
      //...
      }
  }
}


Enter fullscreen mode Exit fullscreen mode

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)
    }
  }
}


Enter fullscreen mode Exit fullscreen mode

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.

Top comments (2)

Collapse
 
nortski78 profile image
Nortski78

What is queue.append() ?
The only append method I'm familiar with is for the use with the DOM.

Collapse
 
guilherme_ferreiralenzol profile image
Guilherme Ferreira Lenzolari

quede.append() is a method to append the element at the end of the list called queue