Получить возможные пути

Учитывая, что кортежи в структуре данных — это ребра, а значения в кортежах — это узлы графа, можно реорганизовать данные таким образом, чтобы упростить алгоритм:

graph = [edge for es in source.values() for edge in es]

Поскольку в графе могут быть циклы, нам нужно отслеживать узлы, которые уже были посещены. Имея это в виду, рекурсивная функция, находящая все пути от начального узла к конечному узлу, дает граф в виде списка ребер от узла к узлу:

def find_path(start, end, edges, visited=None):
    if visited is None:
        visited = []
    for n1, n2, in edges:
        if n1 == start:
            if n2 == end:
                yield [n1, n2]
            elif n2 not in visited:
                for continuation in find_path(n2, end, edges, visited + [n1]):
                    yield [n1] + continuation

Все это:

source = {
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')]
}

graph = [edge for es in source.values() for edge in es]


def find_path(start, end, edges, visited=None):
    if visited is None:
        visited = []
    for n1, n2, in edges:
        if n1 == start:
            if n2 == end:
                yield [n1, n2]
            elif n2 not in visited:
                for continuation in find_path(n2, end, edges, visited + [n1]):
                    yield [n1] + continuation


print(list(find_path('V1', 'Z1', graph)))

Вывод:

[['V1', 'R1', 'R2', 'R4', 'Z1'], ['V1', 'R1', 'R2', 'R5', 'Z1'], ['V1', 'R1', 'R3', 'R4', 'Z1'], ['V1', 'R1', 'R3', 'R5', 'Z1']]

Обратите внимание, что результат приводится к списку, потому что функция является генератором, она выдает решения по одному. Вызов list() собирает все результаты в одном выводе.

Вы можете использовать рекурсию с генератором:

data = {'node1': [('V1', 'R1')], 'node2': [('R1', 'R2'), ('R1', 'R3')], 'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')], 'node4': [('R4', 'Z1')], 'node5': [('R5', 'Z1')]}
new_data = [i for b in data.values() for i in b]
def lookup(start, end, seen=[], c = []):
   _r = [(a, b) for a, b in new_data if a == start and a not in seen]
   for a, b in _r:
      if b == end:
         yield c+[(a, b)]
      else:
         yield from lookup(b, end, seen=seen+[start], c=c+[(a, b)])

print(list(lookup('V1', 'Z1')))

Вывод:

[
  [('V1', 'R1'), 
   ('R1', 'R2'), 
   ('R2', 'R4'), 
   ('R4', 'Z1')], 
  [('V1', 'R1'),  
   ('R1', 'R2'), 
   ('R2', 'R5'), 
   ('R5', 'Z1')], 
  [('V1', 'R1'), 
   ('R1', 'R3'), 
   ('R3', 'R4'), 
   ('R4', 'Z1')], 
  [('V1', 'R1'), 
   ('R1', 'R3'), 
   ('R3', 'R5'), 
   ('R5', 'Z1')]
]

Следующее решение гораздо менее элегантно и более многословно, чем два других решения, но вот пример реализации, расширяющий различные функции:

def flatten_list(l, out=None):
    """
    Flatten to get a list of all edges:

    in:  [[('V1', 'R1')], [('R1', 'R2'), ('R1', 'R3')]
    out: [('V1', 'R1'), ('R1', 'R2'), ('R1', 'R3')]
    """
    if out is None: out=[]
    for li in l:
        if not isinstance(li, list):
            out.append(li)
        else:
            flatten_list(li, out)
    return out


def get_connected_nodes_from(list_of_edges, from_node):
    """
    Given an input node (string), and list of edges (tuple),
    Return a list of all nodes (list of strings) connected to the input node.
    Note: this is a directed graph. That is, we are only grabbing descendants
          and not all (undirected) edges.

    in:  from_node='R1', list_of_edges=[('V1', 'R1'), ('R1', 'R2'), ('R1', 'R3')]
    out: ['R2', 'R3']
    """
    out = []
    for edge in list_of_edges:
        if edge[0] == from_node:
            out.append(edge[1])
        elif from_node == edge[0]:
            out.append(edge[0])
    return out


def get_all_paths(list_of_edges, node=None, current_path=None, all_paths=None):
    """
    Given a list of edges, this will return all directed paths from start to finish.
    """
    # "Initialize" things on the first time through
    if all_paths is None: all_paths = []; node = list_of_edges[0][0]; current_path = [node,]
    node_descendants = get_connected_nodes_from(list_of_edges, node) 
    if len(node_descendants) == 0:
        all_paths.append(current_path) # append the path when it is a leaf with no descendants
    else:
        [get_all_paths(list_of_edges, node, current_path + [node,], all_paths) for node in node_descendants]
    return all_paths

И используя его:

>>> graph = {
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')],
}
>>> list_of_edges = flatten_list(graph.values())
>>> print (['-->'.join(path) for path in get_all_paths(list_of_edges)])
# ['V1-->R1-->R2-->R4-->Z1', 'V1-->R1-->R2-->R5-->Z1', 'V1-->R1-->R3-->R4-->Z1', 'V1-->R1-->R3-->R5-->Z1']