Depth first search finding most concise path but not shortest by weights in python

Question

I am searching a small graph by directed depth first search and in this test case it finds the most concise path (with fewest nodes) but not the shortest path by TotalDistance and OutdoorDistance. The map is: where the nodes are given a->b (weight1, weight2) weight1 = TotalDistance between nodes and weight2 = OutdoorDistance between nodes. The aim is to find the shortest path while staying below maxTotalDist and maxDistOutdoors constraints.

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)

The test is:

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)

And the search algorithm is essentially:

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

The test testSP4() gives the path sp = ['4', '5'] with distances 20, 10 but the given shortest solution is the path ['4', '3', '5'] where the distances are 8, 4. The depth first search is based on a text book version but I've introduced the weights constraints conditions. I've tried various different arrangements of the conditions (such as changing < to >) but that makes other test cases incorrect. Can someone please help? Thanks in advance.

If you want the shortest path, why are you using depth-first search? Depth-first search doesn't give shortest paths, and there is no good way to adjust it to give shortest paths. — user2357112, Apr 21 '16 at 06:57
Unfortunately it's for an assignment and we're expected to use depth first search. — Berwhale, Apr 21 '16 at 07:00
Then either the assignment is wrong, or you've missed a crucial detail. Perhaps your input graphs have some special property, or you were supposed to switch algorithms partway through your assignment and you glossed over that when reading your assignment text. — user2357112, Apr 21 '16 at 07:06
Have a look at http://stackoverflow.com/questions/22764120/dfs-shortest-path-of-a-maze-in-c to see how DFS can find shortest path — Ken Cheung, Apr 21 '16 at 07:12
I thought that I was keeping track of the current path with "shortest"? — Berwhale, Apr 21 '16 at 07:33
I'm not so interested in the len(path) or len(shortest) but the sumTotDistance(digraph, path) and sumDistOutdoors(digraph, path) for each path and shortest - or do you mean where I do shortest = newPath? — Berwhale, Apr 21 '16 at 08:35
@Berwhale I see, I misinterpreted the question (sorry), I thought you intend to find the solution with fewest nodes (i.e. minimum len(path)) that respects the given maxDistOutdoors and maxTotalDist constraints. (I deleted my comments) — danbanica, Apr 21 '16 at 08:57

score 0 · Answer 1 · answered Apr 22 '16 at 03:09

Well I finally found (using bing!?) a similar base algorithm with differences in position of conditions that actually works. I had tried variations of this but I had not removed the if condition immediately before the recursive call to DFSShortest. This combination of search and conditions actually correctly satisfies our given test cases. Thanks for help.

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

Depth first search finding most concise path but not shortest by weights in python

1 Answers1