FilesExpand file tree

 master

/

BreadthFirstShortestPath.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (45 loc) · 1.7 KB

 master

/

BreadthFirstShortestPath.js

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (45 loc) · 1.7 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

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

}