Advertisement
c-mcbride

shortestPath.js

Mar 3rd, 2024
644
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const adjList = {
  2.     1: [2, 5],
  3.     2: [1, 3, 5],
  4.     3: [2, 4],
  5.     4: [3, 5],
  6.     5: [1, 2, 4],
  7.     6: []
  8. }
  9.  
  10. function aShortestPath(start, end) {
  11.     let queue = [];
  12.     let array = [start];
  13.     let visited = new Set();
  14.     visited.add(start);
  15.     queue.push(array);
  16.    
  17.     while(queue.length > 0){
  18.         let currentPath = queue.shift();
  19.         let currentNode = currentPath[currentPath.length - 1];
  20.        
  21.         if(currentNode === end){
  22.             return currentPath;
  23.         }
  24.        
  25.         let neighbors = adjList[currentNode];
  26.        
  27.         for(let neighbor of neighbors){
  28.             if(!visited.has(neighbor)){
  29.                 let newPath = currentPath.concat(neighbor);
  30.                 visited.add(neighbor);
  31.                 queue.push(newPath);
  32.             }
  33.         }
  34.     }
  35.    
  36.     return false;
  37. }
  38.  
  39. console.log("First Test:");
  40. console.log(aShortestPath(1, 3)); // -> [ 1, 2, 3 ] (One possible solution)
  41. console.log("Second Test:");
  42. console.log(aShortestPath(4, 1)); // -> [ 4, 5, 1 ] (One possible solution)
  43. console.log("Third Test:");
  44. console.log(aShortestPath(6, 1)); // -> false
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement