JavaScript/Graphs/BreadthFirstShortestPath.js at master · TheAlgorithms/JavaScript · GitHub

History

54 lines (45 loc) · 1.65 KB

Raw

import Queue from '../Data-Structures/Queue/Queue'

/**

* Breadth-first approach can be applied to determine the shortest path between two nodes in an equi-weighted graph.

* It searches the target node among all neighbors of the starting node, then the process is repeated on the level of

* the neighbors of the neighbors and so on.

* @see https://en.wikipedia.org/wiki/Breadth-first_search

* @see https://www.koderdojo.com/blog/breadth-first-search-and-shortest-path-in-csharp-and-net-core

export function breadthFirstShortestPath(graph, startNode, targetNode) {

// check if startNode & targetNode are identical

if (startNode === targetNode) {

return [startNode]

}

// visited keeps track of all nodes visited

const visited = new Set()

// queue contains the paths to be explored in the future

const initialPath = [startNode]

const queue = new Queue()

queue.enqueue(initialPath)

while (!queue.isEmpty()) {

// start with the queue's first path

const path = queue.dequeue()

const node = path[path.length - 1]

// explore this node if it hasn't been visited yet

if (!visited.has(node)) {

// mark the node as visited

visited.add(node)

const neighbors = graph[node]

// create a new path in the queue for each neighbor

for (let i = 0; i < neighbors.length; i++) {

const newPath = path.concat([neighbors[i]])

// the first path to contain the target node is the shortest path

if (neighbors[i] === targetNode) {

return newPath

}

// queue the new path

queue.enqueue(newPath)

}

// the target node was not reachable

return []

}

JavaScript/Graphs/BreadthFirstShortestPath.js at master · TheAlgorithms/JavaScript · GitHub

Uh oh!

Uh oh!

JavaScript/Graphs/BreadthFirstShortestPath.js at master · TheAlgorithms/JavaScript · GitHub

Uh oh!

Uh oh!

Expand file tree

Breadcrumbs

BreadthFirstShortestPath.js

Latest commit

History

Breadcrumbs

BreadthFirstShortestPath.js

File metadata and controls