Fastest path in an array

In [29]:

    

import collections

arr = [1, 3, 5, 8, 3, 2, 6, 7, 6, 8, 9]
#arr = [1, 3, 5, 3, 2, 6, 7, 6, 8, 9]


n = len(arr) 
route = [ [n, None] for i in range(n)]

route[0] = [0, 0] 
for i in range(0, n-1):
    for j in range(i+1, i+1+arr[i]):
        #print (j)
        if j >= n:
            continue
            
        if route[j][0] > route[i][0] + 1:
            # Faster route
            route[j][0] = route[i][0] + 1
            route[j][1] = i
            
# Init Path            
path = [arr[n-1]]

# STart from last item
s = route[-1]
parent = s[1]
while (parent!=arr[0]):
    parent = s[1]
    
    path.insert(0, arr[parent])
    s = route[parent]
    
path.insert(0, arr[0])

print ("path", path)


    

    




path [1, 3, 5, 6, 9]

In [ ]: