python - 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，因为它不再在开发中，所以我无法测试上面的代码。它应该可以工作，修改语法不确定性。另外，如果可能的话，我建议在 python 中使用networkx^{[ link ]}进行任何类型的图形操作，因为它更完整，正在积极开发中，并且文档更完整pygraphlib。只是一个建议。