Use the BFS algorithm to explore the graph and output the shortest path
P粉633075725
P粉633075725 2023-09-03 11:42:48
0
2
439
<p>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. <strong>However, I'm having trouble printing the results. </strong></p> <p>The expected output (shortest path) is: PHX -> LAX -> MEX -> BKK</p> <pre class="brush:php;toolbar:false;">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));</pre> <p>With the node as the starting point (site) and the edge as the destination, the graph is undirected</p> <pre class="brush:php;toolbar:false;">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')</pre></p>
P粉633075725
P粉633075725

reply all(2)
P粉232793765

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
    }
}
P粉214176639

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);
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!