函数计算多图中给定长度的路径，不包括回溯

Question

我正在尝试编写一个函数来计算多图中特定类型的路径（因此我的图可能在相同的两个顶点之间有多个边）。我需要计算给定长度

n

的路径，在两个给定顶点

v, w

之间，不包括回溯。我所说的最后一个条件的意思是，如果一条特定的边已经从顶点

v0

遍历到顶点

w0

，那么我不想在任何时候包括从

w0

到

v0

的边在同一条路上。

我认为这应该是对 DFS 的一个相对简单的修改，但我无法弄清楚如何合并固定长度、回溯条件和全局计数。

我试过使用递归算法，但我无法让所有东西同时工作。

Answer 1

首先，让我们确定一个表示。我们需要可以编码的东西：

by starting node
    by ending node
        count of edges

这可以通过具有对称性的整数字典存储在 Python 中，其中

multigraph[x][y] == multigraph[y][x]

对所有

x, y

。如果缺少整数计数，我们可以跳过结束节点。因此，例如，如果

a, b, c, d

是顶点，则以下表示有效的多重图。

{
    a: {b: 3, c: 2, d: 3},
    b: {a: 3, c: 2, d: 1},
    c: {a: 2, b: 2},
    d: {a: 3, b: 1},
}

在这个图中，注意从

a

到

a

满足条件的长路径有很多。这是因为有许多长度为 2 和 3 的潜在循环，并且一旦给定循环在一个方向上遍历一次，它就可以在不违反条件的情况下多次遍历该方向。所以我们可以一遍又一遍地在相似的循环之间来回交换。所以路径的数量随着长度呈指数增长。

请注意，@ravenspoint 的答案是基于 Dijkstra 的算法。这不会找到多次重新访问同一节点的路径。因此它无法处理这个图表。

让我们从一张小图和蛮力开始。如果

multi

是多重图，而

v

是顶点，那么这里是一个列出边的函数。

def edges (multi, v):
    for w, c in multi[v].items():
        for i in range(c):
            yield (w, i)

如果路径

n

的长度非常小，那么对所有路径进行暴力枚举是有意义的。像这样的东西。 （你最初的 DFS 想法。）

def count_paths (multi, n, start, target, seen=None):
    if seen is None:
        seen = {}

    if n == 0:
        if start == target:
            return 1
        else:
            return 0
    else:
        answer = 0
        for v, i in edges(multi, start):
            if (v, start, i) not in seen:
                if (start, v, i) in seen:
                    seen.add((start, v, i))
                    answer += count_paths(multi, v, target, seen)
                    seen.pop((start, v, i))
                else:
                    answer += count_paths(multi, v, target, seen)
        return answer

但是...如果

n

很大怎么办？

更好的算法概述是尝试边缘的每个方向。即填写

seen

，使得对于每一个可能出现在

v

中的

w

、

i

和

seen

恰好其中一个出现在

(v, w, i)

中。然后使用动态规划找到所有路径。 （如果您熟悉转换矩阵，您可以将正确的转换矩阵提高到大

(w, v, i)

的正确幂。不过，这种方法可能只适用于某些编程竞赛。） 算法是修改后的Dijkstra

Answer 2

应用 Dijkstra 寻找最便宜的路径

如果 length = required 则添加到输出

• 路径中链接的增量成本
• 重复直到找不到新的路径，超过长度时停止
• 这是使用@btilly 答案中的示例图运行的屏幕截图

---