在无向加权图中查找两个节点之间所有路径的算法

Question

我有一个这样的无向图：

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只是一个随机字符串作为权重。查找两个节点（顶点）之间的所有路径的功能是命中或未命中，我不明白如何。这是我正在使用的函数：

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

当我给出 findPath(list, "A", "D") 时有效，给出 2 条路径 [ [ 'A', 'C', 'D' ], [ 'A', 'B', 'E', 'D' ] ] 但在 findPath(list, "A", "E") 的情况下不是，只给出一条路径。请告诉我我的代码哪里出了问题。

Answer 1

当您的算法找到目标节点并将其标记为已访问时，它将不可能将该目标再次推入队列（用于替代路径），因此它只能找到相同（最短）长度。

而不是使用一个 visited 集，您只需要检查路径是否没有形成循环，这意味着您应该只检查天气 path[= 中的节点31=] 你正在与.

一个简单的更正就是改变这个：

if (!visited.has(neighbor)) {

至

if (!path.includes(neighbor)) {

...但是这种任务最好用 depth-first 算法来完成，它需要更少的内存。例如，使用递归生成器：

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

在无向加权图中查找两个节点之间所有路径的算法

Algorithm to find all path between two nodes in an undirected weighed graph

javascript

graph

breadth-first-search

undirected-graph