DFS shortest path with backtracking

class FailBowlDFS(object):
    no_path_to_dest = 1e10  # more than any node
 
    def __init__(self, tree, cost):
        self.cost = cost
        self.tree = tree
        self.min_dist = {}
        self.visited = set()
 
    def sub_path_sum(self, root, dest):
        """
        we will be finding the min cost path from the root to the dest
        """
        if root is None:
            return self.no_path_to_dest  # No path from this point
        self.visited.add(root)
        root_min = 1e10
 
        for child_node in self.tree[root]:
            if child_node not in self.visited and child_node != dest:
                # The node has not been visited so traverse it
                subpath_cost = self.sub_path_sum(child_node, dest)
                root_min = min(root_min, self.cost.get((root, child_node)) + subpath_cost)
            elif child_node == dest:
                # Just the cost to the child for this subpath
                root_min = min(root_min, self.cost.get((root, child_node)))
            else:
                if child_node not in self.min_dist:
                    # Back edge, continue discovering the other edges
                    continue
                root_min = min(
                    root_min, self.cost.get((root, child_node)) + self.min_dist[child_node])
        self.min_dist[root] = root_min
        return root_min
 
if '__main__' in __name__:
    tree = {
        1: [2, 6],
        2: [3, 4],
        3: [],
        4: [8, 7, 5],
        5: [7, 6],
        6: [5],
        7: [],
        8: []
    }
    cost = {
        (1, 2): 1,
        (1, 6): 1,
        (2, 3): 2,
        (2, 4): 2,
        (4, 8): 5,
        (4, 7): 3,
        (4, 5): 1,
        (5, 7): 3,
        (6, 5): 8,
        (5, 6): 1
    }
    f_b_dfs = FailBowlDFS(tree, cost)
    min_dist = f_b_dfs.sub_path_sum(1, 7)
    assert min_dist == 6, "The min distance is 3 via 1->2->4->7"
    
    tree = {
        # Chain to the dest
        1: [2],
        2: [3],
        3: [4],
        4: [5],
        # Another subpath to dest
        1: [6],
        6: [4],
    }
    cost = {
        (1,2): 1,
        (2,3): 1,
        (3,4): 1,
        (4,5): 1,
        (1,6): 1,
        (6,4): 1
    }
    f_b_dfs = FailBowlDFS(tree, cost)
    min_dist = f_b_dfs.sub_path_sum(1, 5)
    assert min_dist == 3, "The min distance is 3 via 1->6->4->5"
    
    #  Case 3: back edged cycle:
    tree = {
        1: [2],
        2: [3],
        3: [4],
        # A back cycle thru 7
        4: [5, 7],
        5: [6],
        7: [8],
        8: [2],
        8: [3]
    }
    cost = {
        (1, 2): 1,
        (2, 3): 1,
        (3, 4): 1,
        (4, 5): 1,
        (5, 6): 1,
        (4, 7): 1,
        (7, 8): 1,
        (8, 2): 1,
        (8, 3): 1
    }
    f_b_dfs = FailBowlDFS(tree, cost)
    min_dist = f_b_dfs.sub_path_sum(1, 6)
    assert min_dist == 5, "The min distance is 3 via 1->2->3->4->5->6"
    
    # Failing test case:
    
    tree = {
      1: [2, 5],
      2: [3],
      3: [4],
      4: [5, 6],
      5: [4],
      6: [],
    }
    
    cost = {
        (1, 2): 1,
        (1, 5): 1,
        (2, 3): 1,
        (3, 4): 1,
        (4, 5): 1,
        (4, 6): 1,
        (5, 4): 1
    }
    f_b_dfs = FailBowlDFS(tree, cost)
    min_dist = f_b_dfs.sub_path_sum(1, 6)
    assert min_dist != 3, "The min distance is actually 3 via 1->5->4->6 but the algorithm detected {}".format(min_dist)

Python Fiddle

Python Cloud IDE