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^[链接]来处理Python中的图，因为它更完整，正在积极开发，并且文档也比pygraphlib更全面。这只是一个建议。