如何用深度优先搜索法寻找带权边图的最优路径？

Question

我试图从MIT Course Number 6.0002解"Problem Set 2: Fastest Way to Get Around MIT"：

In this problem set you will solve a simple optimization problem on a graph. Specifically, you will find the shortest route from one building to another on the MIT campus given that you wish to constrain the amount of time you spend walking outdoors (in the cold). [...]

Problem 3: Find the Shortest Path using Optimized Depth First Search

In our campus map problem, the total distance traveled on a path is equal to the sum of all total distances traveled between adjacent nodes on this path. Similarly, the distance spent outdoors on the path is equal to the sum of all distances spent outdoors on the edges in the path.

Depending on the number of nodes and edges in a graph, there can be multiple valid paths from one node to another, which may consist of varying distances. We define the shortest path between two nodes to be the path with the least total distance traveled . You are trying to minimize the distance traveled while not exceeding the maximum distance outdoors.

How do we find a path in the graph? Work off the depth-first traversal algorithm covered in lecture to discover each of the nodes and their children nodes to build up possible paths. Note that you’ll have to adapt the algorithm to fit this problem. [...]

Problem 3b: Implement get_best_path

Implement the helper function get_best_path. Assume that any variables you need have been set correctly in directed_dfs. Below is some pseudocode to help get you started.

if start and end are not valid nodes: 
    raise an error 
elif start and end are the same node: 
    update the global variables appropriately
else:
    for all the child nodes of start
        construct a path including that node
        recursively solve the rest of the path, from the child node to the end node

return the shortest path

我不知道我在用深度优先搜索法寻找最短路径的算法中做错了什么。你知道吗

我尝试了未加权边，它的工作很好，但当我尝试加权边，它不会返回最短路径。你知道吗

def get_best_path(digraph, start, end, path, max_dist_outdoors, best_dist,
                  best_path):
    """
    Finds the shortest path between buildings subject to constraints.

    Parameters:
        digraph: Digraph instance
            The graph on which to carry out the search
        start: string
            Building number at which to start
        end: string
            Building number at which to end
        path: list composed of [[list of strings], int, int]
            Represents the current path of nodes being traversed. Contains
            a list of node names, total distance traveled, and total
            distance outdoors.
        max_dist_outdoors: int
            Maximum distance spent outdoors on a path
        best_dist: int
            The smallest distance between the original start and end node
            for the initial problem that you are trying to solve
        best_path: list of strings
            The shortest path found so far between the original start
            and end node.

    Returns:

        a list of building numbers (in strings), [n_1, n_2, ..., n_k],
        where there exists an edge from n_i to n_(i+1) in digraph,
        for all 1 <= i < k and the distance of that path.

        If there exists no path that satisfies max_total_dist and
        max_dist_outdoors constraints, then return None.
    """
    # TODO
    # put the first node in the path on each recursion
    path[0] = path[0] +  [start]
    # if start and end nodes are same then return the path
    if start == end:
        return tuple(path[0])

    # create a node from the start point name
    start_node = Node(start)

    # for each edge starting at that start node, call the function recursively
    # if the destination node is not already in path
    # and if the best_dist has not been found yet or it is greater than the total distance 
    # current path
    for an_edge in digraph.get_edges_for_node(start_node):
        # get the destination node for the edge
        a_node = an_edge.get_destination()
        # update the total distance traveled so far
        path[1] = path[1] + an_edge.get_total_distance()
        # update the distance spent outside
        path[2] = path[2] + an_edge.get_outdoor_distance()

        # if the node is not in path
        if str(a_node) not in path[0]:
            # if the best_distance is none or greater than distance of current path
            if  path[1] < best_dist and path[2] < max_dist_outdoors:
                new_path = get_best_path(digraph, str(a_node), end, [path[0], path[1], path[2]], max_dist_outdoors, best_dist, best_path)
                if new_path != None:
                    best_dist = path[1]
                    print('best_dist', best_dist)
                    best_path = new_path
    return best_path

Answer 1

def get_best_path(digraph, start, end, path, max_dist_outdoors, best_dist, best_path):
    start_node = Node(start)                                                                                                                                                                                     
    end_node = Node(end)                                                                                                                                                                                         
    path[0] = path[0] + [start]                                                                                                                                                                                  
    if len(path[0]) > 1:                                                                                                                                                                                         
        dist, out_dist = get_distances_for_node(digraph, Node(path[0][-2]), start_node)                                                                                                                          
        path[1] = path[1] + dist                                                                                                                                                                                 
        path[2] = path[2] + out_dist                                                                                                                                                                             
    if not digraph.has_node(start_node) and not digraph.has_node(end_node):                                                                                                                                      
        raise ValueError('The graph does not contain these nodes')                                                                                                                                               
    elif start_node == end_node:                                                                                                                                                                                 
        return (path[0], path[1])                                                                                                                                                                                
    else:                                                                                                                                                                                                        
        for an_edge in digraph.get_edges_for_node(start_node):                                                                                                                                                   
            next_node = an_edge.get_destination()                                                                                                                                                                
            if str(next_node) not in path[0]:                                                                                                                                                                    
                expected_dist = path[1] + an_edge.get_total_distance()                                                                                                                                           
                expected_out_dist = path[2] + an_edge.get_outdoor_distance()                                                                                                                                     
                if expected_dist < best_dist and expected_out_dist <= max_dist_outdoors:                                                                                                                         
                    #print('best_path_check', path[1], best_dist)                                                                                                                                                
                    new_path = get_best_path(digraph, str(next_node), end, [path[0], path[1], path[2]], max_dist_outdoors, best_dist, best_path)                                                                 
                    #print(new_path)                                                                                                                                                                             
                    if new_path[0] != None:                                                                                                                                                                      
                        best_path = new_path[0]                                                                                                                                                                  
                        best_dist = new_path[1]                                                                                                                                                                  
    return (best_path, best_dist)    

def get_distances_for_node(digraph, src, dest):                                                                                                                                                                                                                                                                                                                                                         
    for an_edge in digraph.get_edges_for_node(src):                                                                                                                                                              
        if an_edge.get_destination() == dest:                                                                                                                                                                    
            return an_edge.get_total_distance(), an_edge.get_outdoor_distance()     

我能用这个函数解决我的问题，但我不确定它是否是最好的解决方案。 希望这有帮助。你知道吗