Tree in array shortest path.

solution.py

# pip install Dijkstar python-constraint

from constraint import *
from dijkstar import Graph, find_path

tam = 10
problem = Problem()

variables = []
for i in range(tam):
    variables.append(f'{i}')

def max_var_size(index, tam):
    return tam - int(index) - 1

for index, v in enumerate(variables):
    if index == len(variables) - 1:
        problem.addVariable(v, [0])
    else:
        problem.addVariable(v, range(1, max_var_size(index, tam) + 1))

def is_valid(*args):
    return True

problem.addConstraint(is_valid, variables)

solutions = []

for sol in problem.getSolutions():
    s = []
    for i in range(tam):
        s.append(sol[str(i)])
    print(s)
    solutions.append(s)

for sol in solutions:
    labels = [f'v{i}' for i in range(len(sol))]
    graph = Graph()
    for i, a in enumerate(sol):
        labels_interno = labels[i+1:i+a+1]
        for j, b in enumerate(sol[i+1:i+a+1]):
            graph.add_edge(labels[i], labels_interno[j], 1)

    shortest = find_path(graph, labels[0], labels[-1])
    print(sol, shortest.total_cost)
    print()