Блог

Я новичок в программировании, и я пытаюсь найти все возможные пути между 2 узлами, в которых сумма веса ребер меньше заданного значения. Я реализовал свой график в NetworkX, и узлы не имеют никакого веса. Есть ли какая-либо предопределенная функция в NetworkX, которую я могу использовать, или мне нужно написать свой собственный алгоритм для того же, и если я это сделаю, какой будет наилучший подход для того же?

Редактировать: код прямо сейчас просто считывает входные значения и добавляет ребра вместе с их соответствующим весом с помощью метода add_edge, определенного в NetworkX. Я также пытаюсь понять код для метода all_simple_paths_graph, определенного в NetworkX, чтобы изменить его, чтобы сохранить вкладку веса, но пока мало продвинулся вперед, будучи новичком в Python.

Нашел простую реализацию для этого, изменив существующую функцию 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()