Все пути между 2 узлами на основе веса края - PullRequest
Новая
       2

Все пути между 2 узлами на основе веса края

0 голосов
/ 13 апреля 2019

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

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

1 Ответ

0 голосов
/ 13 апреля 2019

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