Utilisez l'algorithme BFS pour explorer le graphique et générer le chemin le plus court

Question

L'objectif du programme est de traverser différents aéroports et d'afficher le chemin le plus court entre PHX et BKK à l'aide d'un algorithme de recherche en largeur. Cependant, j'ai du mal à imprimer les résultats.

Le résultat attendu (chemin le plus court) est : PHX ->

const aéroports = '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'],
];


//Le graphique
const adjacencyList = new Map();

//Ajouter un nœud
fonction addNode (aéroport) {
    adjacencyList.set(aéroport, []);
}

// Ajout d'un bord, non orienté
function addEdge (origine, destination) {
    adjacencyList.get(origin).push(destination);
    adjacencyList.get(destination).push(origine);
}

// Créer le graphique
aéroports.forEach(addNode);
// boucle sur chaque itinéraire et répartit les valeurs dans la fonction addEdge
routes.forEach(route => addEdge(...route));

Avec le nœud comme point de départ (site) et le bord comme destination, le graphique n'est pas orienté

function bfs(start) {
    const visité = new Set();
    visited.add(start); // Ajoute le nœud de démarrage à la liste visitée
    const file d'attente = [début] ;

    while (queue.length > 0) {

        const aéroport = file d'attente.shift(); // changer la file d'attente
        const destinations = adjacencyList.get(aéroport);

        pour (const destination des destinations) {

            si (destination === 'BKK') {
                console.log(`BFS a trouvé Bangkok !`)
                //console.log(chemin);
                
            }

            si (!visited.has(destination)) {
                visité.ajouter(destination);
                file d'attente.push(destination);
                
            }
        }
    }
}

bfs('PHX')

Answer 1

J'ai pu résoudre le problème en suivant les suggestions d'InSync dans les commentaires

Dans la fonction bfs(), oldpath est utilisé pour stocker le chemin parcouru par chaque nœud (nœud parent), et le chemin le plus court est utilisé pour stocker le résultat

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

        }
    }
}

La fonction de la nouvelle fonction est très simple. Ajoutez le nœud parent au chemin le plus court, puis recherchez le nœud parent du nœud parent (s'il existe), et la boucle se termine lorsque le nœud parent actuel est le nœud racine

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

Au lieu de marquer un nœud comme visité, profitez de cette opportunité pour marquer le nœud avec son parent. Vous pouvez utiliser une carte pour :

• Indique si le nœud a été visité
• Indique le nœud précédent (nœud parent) avant d'atteindre
• Maintenir l'ordre des nœuds consultés dans une file d'attente

Je recommande également d'éviter de référencer des variables globales dans les fonctions et de passer plutôt tout le nécessaire en paramètres :

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