The shortest path - BFS
Tags: javascript, bfs, dfs
Published: 2020-09-24 02:52:09


In a [previous blog](https://dev.to/foqc/plotting-a-binary-tree-in-javascript-47hc), I talked about 2 types of search algorithms, for the tree data structure, which were, the **Depth First Search - DFS** and **Breath First Search DFS**, and I mentioned that the The most **efficient algorithm to find the shortest path is BFS**, this algorithm starts from the root and goes through each node by levels instead of branches as DFS does, **using a queue** to temporarily store the nodes. On the other hand, with the DFS algorithm, one must go completely branch by branch, so it would be necessary to store each solution found and at the end obtain the solution that has the shortest path.

##The problem 
*There is a list of words and that given the start and end word, the shortest path must be found, starting from the beginning to the end, the only 2 rules are, while looking for the shortest path, only one letter it can be changed at the same time and the intermediate words that are generated must exist in the word list.*

**Note:** This blog is a JavaScript version of [JavaByPatel blog](https://javabypatel.blogspot.com/2017/05/bfs-vs-dfs-with-example-in-java.html).

A simple example is shown below:
**start word** = CAT
**final palatra** = DOG
**list** = CAT, BAT, COT, COG, COW, RAT, BUT, CUT, DOG, WEB

A path could be the following, **CAT - RAT - BAT - BUT - CUT - COT - COG - DOG,** however the shortest path is, **CAT - COT - COG - DOG**, BFS algorithm allows go through the shortest path, below is the implementation of this algorithm with its respective explanation.

First, to determine that in a word, only one letter has been changed at a time, the following function is implemented.
```javascript
function differByOne(word, target) {
    if (word.length !== target.length) return false
    let diffCount = 0
    
    for (let i = 0; i < word.length; i++) {
        if (target.charAt(i) !== word.charAt(i))
            diffCount++
    }
    
    return diffCount === 1
}
```

Next, BFS is implemented, to find the shortest path.
```javascript
function checkWords(words, start, target) {
    if (!words.has(start) || !words.has(target)) return null
    
    const queue = []
    const path = []
    
    path.push(start)
    queue.push(path)
    words.delete(start)
    
    while (queue.length) {
        const lastPath = queue.shift()
        const lastWord = lastPath[lastPath.length - 1]
        
        if (target == lastWord) return lastPath
        
        for (let item of words) {
            if (differByOne(item, lastWord)) {
                const newPath = [...lastPath]
                newPath.push(item)
                queue.push(newtPath)
                words.delete(item)
            }
         }
    }
    
    return null
}
```
- The **checkWords** function receives 3 parameters, the first is the list of words which is a data type **Set**, the start and target word.
- Check if the word list **does NOT contain** the initial or target word, to immediately return null, **(!Words.has(start) ||! Words.has(target))**.
- Declare an array, which **will be used as a queue** to store the shortest path.
- Declare an **array called path**, to store the selected words.
- **Add to the path**, the start word, **path.push(start)**.
- Add the **new path to the queue**.
- Removes the first selected word **words.delete(start)** from the word list.
- As long as **there is data in the queue**, while (queue.length), the following is done.
- Removes the first path (word list) from the queue and returns it, to the **lastPath constant**.
- The last selected word is obtained from the word list obtained in the previous step, **const lastWord = lastPath [lastPath.length - 1]**.
- If the last **selected word is the final word** that is being searched, it returns the list of words obtained (shortest path) **if(target == lastWord) return lastPath**, in case it is not fulfilled, continue with the following instructions.
- The following is done for every word in the word list.
- Verify that the current word (item) in the word list only has a different letter with respect to the last selected word (lastWord), **differByOne(item, lastWord)**.
- In case the previous condition is met, create a new list (new path) with the words of the last path found (list of words - lastPath) **const newPath = [... lastPath]**.
- To the new path, the word that meets the condition explained in previous item, **newPath.push(item)**, is added.
- The new path is added to the queue, **queue.push(newtPath)**.
- Delete the selected word from the word list, **words.delete(item)**.
- In case the final word is not found during the repetitive cycle, **null is returned**.

Done!, it's time to test the functionality of the algorithm explained above, as shown below.
```javascript
const words = new Set(['BUT', 'CUT', 'RAT', 'BAT', 'WEB', 'CAT', 'COT', 'COG', 'COW', 'DOG'])
const start = 'CAT'
const target = 'DOG'

console.log(checkWords(words, start, target))

// output
// ["CAT", "COT", "COG", "DOG"]
```
The previous code calls the **checkWords** function, the list of words is sent in a data structure of **type Set**, the initial and target words to be searched, the result is printed in the console. **The result will be the shortest path found from the starting word to the end.**


The source code is on [GitHub](https://github.com/foqc/shortest-path).

Was it useful? Show your support and share it.

Stay safe and thank you so much for reading!