| 9 | * @see https://www.koderdojo.com/blog/breadth-first-search-and-shortest-path-in-csharp-and-net-core |
| 10 | */ |
| 11 | export function breadthFirstShortestPath(graph, startNode, targetNode) { |
| 12 | // check if startNode & targetNode are identical |
| 13 | if (startNode === targetNode) { |
| 14 | return [startNode] |
| 15 | } |
| 16 | |
| 17 | // visited keeps track of all nodes visited |
| 18 | const visited = new Set() |
| 19 | |
| 20 | // queue contains the paths to be explored in the future |
| 21 | const initialPath = [startNode] |
| 22 | const queue = new Queue() |
| 23 | queue.enqueue(initialPath) |
| 24 | |
| 25 | while (!queue.isEmpty()) { |
| 26 | // start with the queue's first path |
| 27 | const path = queue.dequeue() |
| 28 | const node = path[path.length - 1] |
| 29 | |
| 30 | // explore this node if it hasn't been visited yet |
| 31 | if (!visited.has(node)) { |
| 32 | // mark the node as visited |
| 33 | visited.add(node) |
| 34 | |
| 35 | const neighbors = graph[node] |
| 36 | |
| 37 | // create a new path in the queue for each neighbor |
| 38 | for (let i = 0; i < neighbors.length; i++) { |
| 39 | const newPath = path.concat([neighbors[i]]) |
| 40 | |
| 41 | // the first path to contain the target node is the shortest path |
| 42 | if (neighbors[i] === targetNode) { |
| 43 | return newPath |
| 44 | } |
| 45 | |
| 46 | // queue the new path |
| 47 | queue.enqueue(newPath) |
| 48 | } |
| 49 | } |
| 50 | } |
| 51 | |
| 52 | // the target node was not reachable |
| 53 | return [] |
| 54 | } |