如何找到有向图中从某个顶点开始长度不超过k的所有简单路径？

Question

我正在尝试找到给定长度的所有简单路径，并致力于使用 BFS 来解决这个问题。但是，我不确定要使用的具体算法。看来BFS并不能轻易解决这个问题。我发现的所有问题都是关于寻找两个给定顶点之间的路径。

但是，我想知道如何找到从有向图中的给定顶点开始、长度达到给定 k 的所有简单路径。不允许循环。

k 长度意味着 k 跳，而不是路径的权重。

例如，我们有 k = 3，给定顶点 1，我们想要找到长度为 k = 1、k = 2、k = 3 的路径。

当k = 1时，我们有路径12和13；当k = 2时，我们有路径132和134；当 k = 3 时，我们找不到合适的路径。

我可以用什么算法来解决这个问题？

Answer 1

这是 Yen 算法的伪代码

IMPORT graph, source and sink
CLEAR vShortestPaths
calculate shortest path from source to sink, add to vShortestPaths
WHILE TRUE
   CLEAR vPotentialPaths
   SET work = graph
   LOOP PF over vShortestPaths
       LOOP spur over PF
            REMOVE out edge from spur in work used by PF
            calculate spurPath, shortest path from spur to sink in work
            IF spurPath exists
                CONTINUE to next iteration of LOOP spur
            SET newPath to combination of source to spur in PF and spurPath
            IF newPath NOT in vShortestPaths
                ADD newPath to vPotentialPaths
            END LOOP spur
        END LOOP PF
    IF vPotentialPaths NOT empty
        ADD shortest path in vPotentialPaths to vShortestPaths
    END WHILE TRUE 

Answer 2

为此，您将使用深度优先遍历。递归函数是自然的选择。它会重复到深度

k

，然后产生它走过的路径。在每次递归调用时，请确保不要将节点添加到路径上已有的路径中。当您退出递归调用时，相应地减少路径。

这是 JavaScript 中的一个实现，其中递归函数将邻接列表（表示图）、当前节点、

k

的值和作为 Set（有序哈希集）的路径作为参数。

function* genPaths(adj, node, k, path=new Set) {
    if (path.has(node)) return; // cycle detected!
    if (k == 0) return yield [...path, node]; // We have a result
    path.add(node);
    for (const neighbor of adj[node]) {
        yield* genPaths(adj, neighbor, k - 1, path);
    }
    path.delete(node); // backtrack
}

// Demo
const adj = {
    "1": ["2", "3"],
    "2": [],
    "3": ["2", "4"],
    "4": ["3"]
};

// Finding paths with k=1, k=2 and k=3:
for (let k = 1; k <= 3; k++) {
    console.log("results for k =", k);
    for (const path of genPaths(adj, "1", k)) {
        console.log("  ", ...path);
    }
}
console.log("done");

延长它...

上面的函数返回 exactly

k

长度的路径，主代码使用它来获取几个不同长度的路径。如果您总是对所有较短的路径感兴趣，甚至包括大小为 0 的路径（只是起始节点），那么您可以扩展该函数以通过一个顶级调用来完成所有这些操作：

function* genPaths(adj, node, k, path=new Set) {
    if (path.has(node)) return; // cycle detected!
    yield [...path, node]; // We have a result (0 <= path size <= k)
    if (k == 0) return;
    path.add(node);
    for (const neighbor of adj[node]) {
        yield* genPaths(adj, neighbor, k - 1, path);
    }
    path.delete(node); // backtrack
}

// Demo
const adj = {
    "1": ["2", "3"],
    "2": [],
    "3": ["2", "4"],
    "4": ["3"]
};

// Finding paths with size <= 3:
for (const path of genPaths(adj, "1", 3)) {
    console.log("  ", ...path);
}
console.log("done");

请注意，路径的大小表示为其上边的数量，因此 [1] 是长度为 0 的路径，[1, 3] 是长度为 1 的路径，...等等。