Use the BFS algorithm to explore the graph and output the shortest path

Question

The goal of the program is to pass through various airports and output the shortest path between PHX and BKK using a breadth-first search algorithm. However, I'm having trouble printing the results.

The expected output (shortest path) is: PHX -> LAX -> MEX -> BKK

const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');

const routes = [
    ['PHX', 'LAX'],
    ['PHX', 'JFK'],
    ['JFK', 'OKC'],
    ['JFK', 'HEL'],
    ['JFK', 'LOS'],
    ['MEX', 'LAX'],
    ['MEX', 'BKK'],
    ['MEX', 'LIM'],
    ['MEX', 'EZE'],
    ['LIM', 'BKK'],
];


//The graph
const adjacencyList = new Map();

//Add node
function addNode(airport) {
    adjacencyList.set(airport, []);
}

// Add edge, undirected
function addEdge(origin, destination) {
    adjacencyList.get(origin).push(destination);
    adjacencyList.get(destination).push(origin);
}

// Create the Graph
airports.forEach(addNode);
// loop through each route and spread the values ​​into addEdge function
routes.forEach(route => addEdge(...route));

With the node as the starting point (site) and the edge as the destination, the graph is undirected

function bfs(start) {
    const visited = new Set();
    visited.add(start); // Add the start node to the visited list
    const queue = [start];

    while (queue.length > 0) {

        const airport = queue.shift(); // change queue
        const destinations = adjacencyList.get(airport);

        for (const destination of destinations) {

            if (destination === 'BKK') {
                console.log(`BFS found Bangkok!`)
                //console.log(path);
                
            }

            if (!visited.has(destination)) {
                visited.add(destination);
                queue.push(destination);
                
            }
        }
    }
}

bfs('PHX')

Answer 1

I was able to resolve the issue by following InSync's suggestions in the comments

In the bfs() function, oldpath is used to store the path followed by each node (parent node), and shortest path is used to store the result

const oldpath = new Map();
let shortestPath = [];

while (queue.length > 0) {

        let airport = queue.shift(); // mutates the queue
        const destinations = adjacencyList.get(airport);

        for (const destination of destinations) {
            // destination -> origin
            if (destination === 'BKK')  {
                console.log(`BFS found Bangkok!`)
                oldpath.set(destination, airport) // remember parentNode    
                retracePath(airport);    // loops through all parentNodes of BKK 
                                          //   and adds them to the path
                console.log(shortestPath);
                shortestPath = []
            }

            if (!visited.has(destination)) {
                oldpath.set(destination, airport) // remember parentNode
                visited.add(destination);
                queue.push(destination);
            }

        }
    }
}

The function of the new function is very simple. Add the parent node to shortestPath, then find the parent node of the parent node (if it exists), and the loop exits when the current parent node is the root node

function retracePath(parentNode){
    while(oldpath.get(parentNode)){ // keep going until reaching the root
        shortestPath.unshift(parentNode); // adding each parent to the path 
        parentNode = oldpath.get(parentNode); // find the parent's parent
    }
}

Answer 2

Instead of marking a node as visited, use this opportunity to mark the node with its parent. You can use a Map to:

• Indicates whether the node has been visited
• Indicates the previous node (parent node) before reaching
• Maintain the order of accessing nodes in a queue

I also recommend avoiding referencing global variables in functions and instead passing everything needed as arguments:

function createGraph(airports, routes) {  // Your code, but as a function
    // The graph
    const adjacencyList = new Map();

    // Add node
    function addNode(airport) {
        adjacencyList.set(airport, []);
    }

    // Add edge, undirected
    function addEdge(origin, destination) {
        adjacencyList.get(origin).push(destination);
        adjacencyList.get(destination).push(origin);
    }

    // Create the Graph
    airports.forEach(addNode);
    // loop through each route and spread the values into addEdge function
    routes.forEach(route => addEdge(...route));
    return adjacencyList;
}


function bfs(adjacencyList, start, end) {
    const cameFrom = new Map(); // Used as linked list, as visited marker, and as queue
    cameFrom.set(start, null);
    // As Map maintains insertion order, and keys() is an iterator,
    //   this loop will keep looping as long as new entries are added to it
    for (const airport of cameFrom.keys()) {
        for (const destination of adjacencyList.get(airport)) {
            if (!cameFrom.has(destination)) {
                cameFrom.set(destination, airport); // remember parentNode
                if (destination === end) return retracePath(cameFrom, end);
            }
        }
    }
}

function retracePath(cameFrom, node) {
    const path = [];
    while (cameFrom.has(node)) {
        path.push(node);
        node = cameFrom.get(node);
    }
    return path.reverse();
}

const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');

const routes = [
    ['PHX', 'LAX'], 
    ['PHX', 'JFK'],
    ['JFK', 'OKC'],
    ['JFK', 'HEL'],
    ['JFK', 'LOS'],
    ['MEX', 'LAX'],
    ['MEX', 'BKK'],
    ['MEX', 'LIM'],
    ['MEX', 'EZE'],
    ['LIM', 'BKK'],
];

const adjacencyList = createGraph(airports, routes); 
const path = bfs(adjacencyList, 'PHX', 'BKK');
console.log(path);