def best_path (o, R, CT, Delta, parms, start_time):
    S_end = [].copy()
    T_end = None
    Cmax_end = 0
    smax_end = 0
    

    while True:
        Front = get_initial_front_0 (R)
        #Front = get_initial_front_N (R)
        #Front = get_initial_front_fringe (R)
        #Front = get_initial_front_all (R)

        if Front != None:
            S_end, Cmax, smax = best_path_aux (S_end, Front, Delta, parms, start_time)

            if S_end == None or S_end == -3:
                T_end = None
                break
            else:
                T_end = S_end[len(S_end)-1]['Tend']
            if Cmax > Cmax_end:
                Cmax_end = Cmax
                smax_end = smax
        else:
            break      
    
    return S_end, T_end, Cmax_end, smax_end

def best_path_aux (S, Front, Delta, parms, start_time):
    ind = 2 * len(S)
    indx = ' ' * ind

    if len(Front) == 0:
        return S, 0, None

    N = len(S)
    if N == 0:
        Tend = 0
        qend = None
    else:
        Tend = S[len(S)-1]['Tend']
        rbitend = S[len(S)-1]['rbit']
        qend = S[len(S)-1]['p'][1-rbitend]

    Cands = [].copy() #List of pairs (stroke, reversebit) 

    for i in range(len(Front)):
        assert Front[i]['rbit'] == 0

        Cands.append((Front[i], 0, air_time(calculate_distance(qend, Front[i]['p'][0]), parms)))
        Cands.append((Front[i], 1, air_time(calculate_distance(qend, Front[i]['p'][1]), parms)))

    
    Cands = exclude_bad_candidates (qend, Tend, Cands, Front, Delta, ind, parms, start_time)
    #Cands = sort_candidates_raster (qend, Cands)
    Cands = sort_candidates_dist (qend, Cands)
    #Cands = sort_candidates_none (qend, Cands)

    if len(S) == 99999:
        print_cands (Cands, ind)
        sys.exit()

    #if (time.time() - start_time) > 3600:
    #   return -3, 0, 0

    for k in range(len(Cands)):
        Ck = Cands[k]
        Rk = Ck[0]
        assert Rk['rbit'] == 0
        rbitk = Ck[1]
        pk = Rk['p'][rbitk]
        qk = Rk['p'][1-rbitk]
        ek = Rk['e']
        assert Rk['Tini'] == None
        assert Rk['Tend'] == None

        if qend != None:
            Tinik = Tend + Ck[2]#air_time (calculate_distance(qend, pk), parms)
        else:
            Tinik = 0

        Rk['Tini'] = Tinik
        Tendk = Tinik + ek
        Rk['Tend'] = Tendk
        qend = qk
        Rk['rbit'] = rbitk
        S.append(Rk)

        if verbose:
           sys.stderr.write("%s---------------------------------------------\n" % indx)
           print_stroke (Rk, 0, 'appended', ind)
           sys.stderr.write("%s---------------------------------------------\n" % indx)
        else:
           sys.stderr.write("%sappended R%03d:%d, Tini = %.6f, Tend = %.6f \n" % (indx, Rk['sid'], Rk['rbit'], Rk['Tini'], Rk['Tend']))
        
        Cmax_k, smax_k = worst_cooling_one (Rk)
        NewFront = update_front_h2 (Front, Rk)
        S_rec, Cmax_rec, smax_rec = best_path_aux (S, NewFront, Delta, parms)

        if S_rec != None:
            if Cmax_rec > Cmax_k:
                return S_rec, Cmax_rec, smax_rec
            else:
                return S_rec, Cmax_k, smax_k
        else:
            Rk['rbit'] = 0
            Rk['Tini'] = None
            Rk['Tend'] = None
            S.pop()

            if verbose:
               sys.stderr.write("%s---------------------------------------------\n" % indx)
               print_stroke (Rk, rbitk, 'deleted', ind)
               sys.stderr.write("%s---------------------------------------------\n" % indx)
            else:
               sys.stderr.write("%sdeleted R%03d:%d \n" % (indx, Rk['sid'], rbitk))

    sys.stderr.write("%s**FAILED\n" % indx)
    return None, None, None