I have an undirected graph like this:
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 is just a random string as weight. The function to find all path between two nodes(vertices) is a hit a hit or a miss and I don't understand how.
Here's the function I'm using:
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;
}
It works when I give findPath(list, "A", "D"), giving 2 paths
[ [ 'A', 'C', 'D' ], [ 'A', 'B', 'E', 'D' ] ]
but not in the case of findPath(list, "A", "E"), giving only one path. Please tell me where my code malfunctions.
When your algorithm finds the target node, and marks it as visited, it will be impossible for it to push that target another time (for an alternative path) on the queue, and so it can only find paths of the same (shortest) length.
Instead of using one visited set, you need to only check that a path is not making a cycle, which means you should only check weather a node is in the path you are working with.
A simple correction is to change this:
if (!visited.has(neighbor)) {
to
if (!path.includes(neighbor)) {
...but this kind of task can better be done with a depth-first algorithm, which needs less memory. For instance, with a recursive generator:
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")]);