基于边权重的两个节点之间的所有路径

Question

我是一个新的编程，我试图找到所有可能的路径之间的2个节点的重量之和是小于一个给定的值。我已经在NetworkX中实现了我的图，节点没有任何权重。NetworkX中是否有我可以使用的预定义函数，或者我需要为相同的函数编写自己的算法，如果我这样做了，对于相同的函数，最好的方法是什么？你知道吗

编辑：现在的代码只是读取输入值，并通过NetworkX中定义的add\u edge方法添加边及其各自的权重。 我还试图理解NetworkX中定义的所有\u简单路径\u图形方法的代码，以便对其进行修改以保持权重，但迄今为止进展甚微，这对Python来说是新的。你知道吗

Answer 1

通过修改NetworkX的现有函数，找到了一个简单的实现方法。 此函数用于打印给定节点之间的所有路径，沿这些路径，边的权重之和不超过给定值。你知道吗

def all_paths(G, source, target, w):
    cutoff = len(G)-1
    visited = [source]
    stack = [iter(G[source])]
    weight = 0
    while stack:
        children = stack[-1]
        child = next(children, None)
        if child is None:
            stack.pop()
            visited.pop()
        elif len(visited) < cutoff:
            if child == target:
                if (visited[-1],child) in G.nodes():
                    temp = G[visited[-1]][child]['weight']
                else:
                    temp = G[child][visited[-1]]['weight']
                if weight+temp <= w:
                    yield visited + [target]
            elif child not in visited:
                if (visited[-1],child) in G.nodes():
                    weight += G[visited[-1]][child]['weight']
                else:
                    weight += G[child][visited[-1]]['weight']
                visited.append(child)
                stack.append(iter(G[child]))
        else: 
            if child == target or target in children:
                if (visited[-1],child) in G.nodes():
                    temp = G[visited[-1]][child]['weight']
                else:
                    temp = G[child][visited[-1]]['weight']
                if weight+temp <= w:
                    yield visited + [target]
            stack.pop()
            visited.pop()