gistfile1.py

# This is a proposed implementation of single source shortest path using DFS

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"
    print f_b_dfs.min_dist
    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"
    print f_b_dfs.min_dist
    
        #  Case 3: back edged cycle:
    tree = {
        1: [2],
        2: [3],
        3: [4],
        # A back cycle thru [I7
        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"
    print f_b_dfs.min_dist

So a few things. The algorithm is built for single pair shortest path from a source to destination:

• The algorithm ignores nodes that are reachable via back edges when its recursively descending from source to destination.
• The min_dist is used for memoizing results also acts as a way to detect back edges that may form cycles.
• It does not visit a node twice because of the visited list it keeps as well as min_dist which helps avoid cycles.
• If you want the run the single source shortest path then you will have to run it V times making the algorithm's run time the same as bellman ford. And bellman ford can do negative cycle detection as well so this has less utility.

This algorithm runs in Theta(E) time and consumes O(V) memory for the min_dist dictionary that it keeps to memoize results as well as a for keeping a list of things it has visited.