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

temp_path = []
all_paths = []

def get_all_pathes(a, b, graph):
    if b in graph[a]:
        all_paths.append(temp_path + [a, b])
    else:
        for v in graph[a]:
            if v == b:
                all_paths.append(temp_path + [a, b])
                break
            elif v not in temp_path:
                temp_path.append(a)
                get_all_pathes(v, b, graph)
                del temp_path[-1]
    return None


def shortest_path(a, b, graph):
    get_all_pathes(a, b, graph)
    shortest_path_ = sorted(all_paths, key=len)[0]
    shortest_path_formated = '-'.join(map(str, shortest_path_))
    print(f'Самый короткий путь: {shortest_path_formated}. Сложность: {len(shortest_path_)}')