CODEWITHSUNDEEP
pythonrecursion
user000
user000

Reputation: 49

Recursion. Find all longest path given a starting point and a maximum distance

Given a starting point A and a maximum distance D, what are/is the longest path(s) starting from A which have a length superior or equal to D. What is wrong with this piece of code ?

def find_paths(graph, start, path, allpaths, dmax):
    if dmax == 0:
        allpaths.append([start])
    else:
        path.append(start)
        for edge in graph[start]:
            d = graph[start][edge]
            if dmax - d >= 0:
                find_paths(graph, edge, path, allpaths, dmax - d)
            else:
                allpaths.append(path)
    return allpaths

graph = { 
          1: {2: 33, 3: 15},
          2: {1: 33, 4: 57, 5: 7},
          3: {1: 15},
          4: {2: 57},
          5: {1: 89, 2: 7},
        }

print find_paths(graph, 1, [], [], 50)

This gives:

[[1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3], [1, 2, 5, 2, 3, 1, 3]]

The output from find_paths(graph, 1, [], [], 50) should be (1, 3) and (1, 2, 5). That is, the two path that go through the vertices 1 and 3 for the first, 1, 2 and 5 for the second one.

Thank you.

Upvotes: 0

Views: 474

Answers (1)

Amy Teegarden
Amy Teegarden

Reputation: 3972

One big problem is that you are appending to path, then passing it to the next iteration of the recursion. That's why you're getting the same result for every path. You need to create a new path each time. 

def find_paths(graph, start, path, allpaths, dmax):
    if dmax == 0:
        allpaths.append([start])
    else:
        newpath = path + [start]
        for edge in graph[start]:
            d = graph[start][edge]
            if dmax - d >= 0:   
                find_paths(graph, edge, newpath, allpaths, dmax - d)
            else:
                allpaths.append(newpath + [edge])
    return allpaths

graph = { 
          1: {2: 33, 3: 15},
          2: {1: 33, 4: 57, 5: 7},
          3: {1: 15},
          4: {2: 57},
          5: {1: 89, 2: 7},
        }

print find_paths(graph, 1, [], [], 50)

Additionally, I'm not sure why you're expecting the result to be (1, 3) and (1, 2, 5). It looks to me like (1, 3) has a length of 15.

Upvotes: 1

Related Questions