深度优先搜索在python中找到最简洁的路径，但不是按权重计算的最短路径

Question

我通过定向深度优先搜索来搜索一个小图，在这个测试用例中，它找到了最简洁的路径（节点最少），但不是TotalDistance和OutdoorDistance的最短路径。映射为：其中节点给定a->b（weight1，weight2）weight1=节点之间的TotalDistance，weight2=节点之间的OutdoorDistance。其目的是在低于maxTotalDist和maxDistOutdoors约束的情况下找到最短路径。

1->2 (5.0, 2.0)
3->5 (6.0, 3.0)
2->3 (20.0, 10.0)
2->4 (10.0, 5.0)
4->3 (2.0, 1.0)
4->5 (20.0, 10.0)

测试是：

def testSP4():
    nodes = []
    for name in range(1,6):
        nodes.append(Node(str(name)))
    g = WeightedDigraph()
    for n in nodes:
        g.addNode(n)
    g.addEdge(WeightedEdge(nodes[0],nodes[1], 5.0, 2.0))
    g.addEdge(WeightedEdge(nodes[2],nodes[4], 6.0, 3.0))
    g.addEdge(WeightedEdge(nodes[1],nodes[2], 20.0, 10.0))
    g.addEdge(WeightedEdge(nodes[1],nodes[3], 10.0, 5.0))
    g.addEdge(WeightedEdge(nodes[3],nodes[2], 2.0, 1.0))
    g.addEdge(WeightedEdge(nodes[3],nodes[4], 20.0, 10.0))
    sp = directedDFS(g, '4', '5', 21, 11)
    print sp
    path = []
    for node in sp:
        path.append(Node(node))
    print sumTotDistance(g, path), sumDistOutdoors(g, path)

搜索算法本质上是：

def DFSShortest(digraph, start, end, maxTotalDist, maxDistOutdoors, dist1 = 0, dist2 = 0, path = [], shortest = None):
    #assumes digraph is a WeightedDigraph
    #assumes start and end are nodes in digraph
    path = path + [Node(start)]
    if Node(start) == Node(end):
        if dist1 <= maxTotalDist and dist2 <= maxDistOutdoors:
            return path
    for [node, (weight1, weight2)] in digraph.edges[Node(start)]:
        if node not in path: #avoid cycles
            if shortest == None or (sumTotDistance(digraph, path) < sumTotDistance(digraph, shortest) 
            and sumDistOutdoors(digraph, path) < sumDistOutdoors(digraph, shortest)):
                newPath = DFSShortest(digraph,node,end, maxTotalDist, maxDistOutdoors, dist1+weight1, dist2+weight2, path, shortest)
                if newPath != None:
                    shortest = newPath
    return shortest

测试testSP4（）给出了距离为20、10的路径sp="4"、"5"]，但给定的最短解决方案是距离为8、4的路径"4"，"3"、"6"。深度优先搜索是基于课本版本的，但我引入了权重约束条件。我尝试了各种不同的条件安排（例如将<更改为>），但这会导致其他测试用例不正确。有人能帮忙吗？提前谢谢。

Answer 1

我终于找到了（使用bing！？）一个类似的基本算法，但条件的位置不同，它实际上有效。我尝试过这种方法的变体，但在递归调用DFSShortest之前，我没有立即删除if条件。这种搜索和条件的组合实际上正确地满足了我们给定的测试用例。谢谢你的帮助。

def DFSShortest(digraph, start, end, maxTotalDist, maxDistOutdoors, dist1 = 0, dist2 = 0, path = [], shortest = None):
    #assumes digraph is a WeightedDigraph
    #assumes start and end are nodes in digraph
    path = path + [Node(start)]
    if Node(start) == Node(end):
        if (dist1 <= maxTotalDist and dist2 <= maxDistOutdoors):
            return path
    for [node, (weight1, weight2)] in digraph.edges[Node(start)]:
        if node not in path: #avoid cycles
            newPath = DFSShortest(digraph,node,end, maxTotalDist, maxDistOutdoors, dist1+weight1, dist2+weight2, path, shortest)
            if newPath:
                if not shortest or (sumTotDistance(digraph, newPath) < sumTotDistance(digraph, shortest)
                and sumDistOutdoors(digraph, newPath) < sumDistOutdoors(digraph, shortest)):
                    shortest = newPath
    return shortest