Python code to find a all paths from given dictionary values-CodePudding

I need to find a way so that i get all possible paths for given set of dictionary values. For example:

In this case we start from point 1 and we want to reach 7:

k = dict()

k[1] = [(1,2),(1,7)]
k[2] = [(2,3),(2,4),(2,5)]
k[3] = [(3,6),(3,7)]

One of the outputs would for example be: [(1,2),(2,3),(3,7)]

I'm really struggling to find a recursive method for this.

CodePudding user response：

You can iterate over k like so. There is probably a better way depending on your actual goal, but this shows how to get to every tuple (t) value:

for key in k.keys():
  for t in k[key]:
    print(f"key = {key}, tuple values = ({t[0]}, {t[1]})")

CodePudding user response：

Model the problem as Graph and perform Depth First search since objective is to achieve via recursion.

graph = { 
    1 : [2, 7], 
    2 : [3, 4, 5], 
    3 : [6, 7], 
    4 : [2],
    5 : [2],
    6 : [3],
    7 : [1, 3]
    }   

vertex = 7 
visited = [False] * (vertex   1)
path = []


def any_path(src, dest, visited, path):

    # Mark the current node as visited and store in path
    visited[src] = True
    path.append(src)

    # If current vertex is same as destination
    if src == dest:
        return True

    # If current vertex is not destination
    # Recursively call for all the vertices adjacent to this vertex
    for neighbor in graph[src]:
        if not visited[neighbor] and any_path(neighbor, dest, visited, path):
            return True

    # Remove current vertex from path[]
    path.pop()
    return False


any_path(1, 7, visited, path)


print (path)

The output of paths will be like this

[1, 2, 3, 7]

We can use pairwise to achieve the desired output of

[(1,2), (2,3), (3, 7)]