Pygraph - путь между двумя узлами с определенным весом

Question

Я хочу найти путь в графе, который соединяет два узла и не использует один и тот же узел дважды.Сумма весов ребер должна находиться в определенном диапазоне.

Мне нужно реализовать это в pygraph .Я не уверен, есть ли уже алгоритм, который я могу использовать для этой цели или нет.Какой лучший способ добиться этого?

Answer 1

РЕДАКТИРОВАТЬ: Я неправильно понял вопрос изначально.Я исправил свой ответ.Эта функциональность не встроена в библиотеку pygraphlib, но вы можете легко реализовать ее.Рассмотрим что-то вроде этого, который в основном получает кратчайший путь, решает, находится ли он в предопределенном диапазоне, затем удаляет ребро с наименьшим весом, вычисляет новый кратчайший путь и повторяет.

from pygraphlib import pygraph, algo

edges = [(1,2),(2,3),(3,4),(4,6),(6,7),(3,5),(4,5),(7,1),(2,5),(5,7)]
graph = pygraph.from_list(edges)

pathList = []
shortestPath = algo.shortest_path(graph, startNode, endNode)
cost = shortestPath[len(shortestPath)-1][1]

while cost <= maxCost:
    if cost >= minCost:
        pathList.append(shortestPath)

    minEdgeWt = float('inf')
    for i in range(len(shortestPath)-1):
        if shortestPath[i+1][1] - shortestPath[i][1] < minEdgeWt:
            minEdgeWt = shortestPath[i+1][1] - shortestPath[i][1]
            edgeNodes = (shortestPath[i][0], shortestPath[i+1][0])

    #Not sure of the syntax here, edgeNodes is a tuple, and hide_edge requires an edge.
    graph.hide_edge(edgeNodes)
    shortestPath = alog.shortest_path(graph, startNode, endNode)
    cost = shortestPath[len(shortestPath)-1][1]

return pathList

Обратите внимание, чтоЯ не смог найти копию pygraphlib, поскольку она больше не разрабатывается, поэтому я не смог протестировать приведенный выше код.Это должно работать, мод неопределенности синтаксиса.Также, если возможно, я бы порекомендовал использовать networkx ^{[ link ]} для любого вида манипулирования графами в python, так как он более полный, в активной разработке и более полно документировантогда pygraphlib.Просто предложение.