Tengo un gráfico no dirigido como este:
let list = new Map([ ["A", [["B", "rdWeight"], ["C", "rdWeight"]]], ["B", [["A", "rdWeight"], ["E", "rdWeight"]]], ["C", [["D", "rdWeight"], ["A", "rdWeight"]]], ["D", [["C", "rdWeight"], ["E", "rdWeight"]]], ["E", [["B", "rdWeight"], ["D", "rdWeight"]]] ]); rdWeight es solo una cadena aleatoria como peso. La función para encontrar todas las rutas entre dos nodos (vértices) es un acierto o un error y no entiendo cómo. Aquí está la función que estoy usando:
function findPath(list, start, end) { let paths = []; let visited = new Set(); let queue = []; queue.push([start, [start]]); while (queue.length > 0) { let [current, path] = queue.shift(); visited.add(current); if (current === end) { paths.push(path); } for (let [neighbor] of list.get(current)) { if (!visited.has(neighbor)) { queue.push([neighbor, [...path, neighbor]]); } } } return paths; } Funciona cuando doy findPath(list, "A", "D") , dando 2 rutas [ [ 'A', 'C', 'D' ], [ 'A', 'B', 'E', 'D' ] ] pero no en el caso de findPath(list, "A", "E") , dando solo una ruta. Por favor, dígame dónde falla mi código.
Cuando su algoritmo encuentre el nodo objetivo y lo marque como visitado, será imposible que empuje ese objetivo otra vez (para una ruta alternativa) en la cola, por lo que solo puede encontrar rutas de la misma longitud (la más corta). .
En lugar de usar un conjunto visited , solo debe verificar que una ruta no esté haciendo un ciclo, lo que significa que solo debe verificar si hay un nodo en la ruta con la que está trabajando.
Una corrección simple es cambiar esto:
if (!visited.has(neighbor)) {a
if (!path.includes(neighbor)) {...pero este tipo de tarea se puede realizar mejor con un algoritmo de profundidad primero, que necesita menos memoria. Por ejemplo, con un generador recursivo:
function* findPath(list, start, end, visited=new Set) { if (start === end) return yield [...visited, end]; visited.add(start); for (let [neighbor] of list.get(start)) { if (!visited.has(neighbor)) { yield* findPath(list, neighbor, end, visited); } } visited.delete(start); } let list = new Map([ ["A", [["B", "rdWeight"], ["C", "rdWeight"]]], ["B", [["A", "rdWeight"], ["E", "rdWeight"]]], ["C", [["D", "rdWeight"], ["A", "rdWeight"]]], ["D", [["C", "rdWeight"], ["E", "rdWeight"]]], ["E", [["B", "rdWeight"], ["D", "rdWeight"]]] ]); console.log([...findPath(list, "A", "E")]);