Question 51160 in Javascript Question posted in
A very good W3school tutorial can be found here.

Printing the Shortest Path After Traversing a Graph Using BFS Algorithm – Javascript

The program goal is to traverse through various airports and output the shortest path between PHX and BKK using Breadth First Search algorithm. However, I am facing difficulty in printing the result.

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));

Adding nodes as the origin(station), and edges as the destination, the graph is undirected

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

    while (queue.length > 0) {

        const airport = queue.shift(); // mutates the 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')
Tags:

2

Answers


  1. Chosen as BEST ANSWER
    0

    I was able to solve the issue following InSync suggestion in the comments

    code in bfs(): oldpath is used to store the path taken for each node (parentNode) 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 new function job is simple, add the parentNode to the shortesPath then find the parent of the parentNode if exists, the loop quits when the current parentNode is the Root

    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
    }
}

  2. 0

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

    • Indicate that a node was visited
    • Indicate which was the previous node before getting there (parent)
    • Maintain an order for visiting nodes in queue fashion

    I would also avoid referencing global variables in functions, and instead pass all that is 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);
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search