The shortest path - BFS

In a previous blog, 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.

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.

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.

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.

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.

Was it useful? Show your support and share it.

Stay safe and thank you so much for reading!