Return to Question

So here I'm looking for a comparison based on the time complexity of the algorithms, related to an analysis of the cases where the number of edges increases, at a fixed number of vertices. There is a reference solution in Python which is correct and fast, but I fail to see where is the fundamental difference between the two algorithms, behind the other minor code differences (also because the languages are different).

Start by receiving the graph topology and starting point
    Define a mindistance variable
    and a list of completed solutions, initially empty

    Start looping at the queue of partial solutions
        So a single partial solution is dequeued
        It computes possible vertices based on current predecessors
        Check if nothing remains and adds it to the completed alternatives otherwise updating mindistance
        Otherwise loop as in classical BFS
        For all possible moves = reachable vertices
                
                For each one applies above said single step
                If done updates mindistance and completed alternatives 
                Otherwise enqueue such partial solution 
                
  
    Finally select the min alternative by distance.

It represents a list of lowercase char vertices with uppercase constrained predecessors and edges weighted by different dotted distances. So here I'm looking for a comparison based on the time complexity of the algorithms, related to an analysis of the cases where the number of edges increases, at a fixed number of vertices. There is a reference solution in Python which is correct and fast, but I fail to see where is the fundamental difference between the two algorithms, behind the other minor code differences (also because the languages are different).

Start by receiving the graph topology and starting point
    Define a mindistance variable
    and a list of completed solutions, initially empty

    Start looping at the queue of partial solutions
        So a single partial solution is dequeued
        It computes possible vertices based on current predecessors
        Check if nothing remains and adds it to the completed alternatives updating mindistance
        Otherwise loop as in classical BFS
        For all possible moves = reachable vertices
                
                For each one applies above said single step
                If done updates mindistance and completed alternatives 
                Otherwise enqueue such partial solution 
                
  
    Finally select the min alternative by distance.

1 single step receives as input which is the move index i
2 then it updates the distance of the current solution draft by summing the distance to the vertex I
3 it updates the current position as of vertex I
4 it also updates the list of predecessors by including vertex i
5 it computes the new tree of reachable vertices starting from the `fullGrid` and taking into account the newly updated list of predecessors

1 single step receives as input which is the move index i
2 then it updates the distance of the current solution draft by summing the distance to the vertex i
3 it updates the current position as of vertex i
4 it also updates the list of predecessors by including vertex i
5 it computes the new tree of reachable vertices starting from the `fullGrid` and taking into account the newly updated list of predecessors

let next (step:Step) (i:int) (solution: Solution) (fullGrid: Map<char,Map<char,Grid>>) : Solution =
    let branches = solution.tree.branches
    let distance = solution.tree.distance + branches.[i].distance
    let area = branches.[i].area  
    //let newbranches, back, keys =
    match step with
    | SpaceStep ->
        failwith "not expected with smart grid"
    | KeyStep ->
        let keys = area :: solution.keys
        let grid = fullGrid.[area]
        let tree = grid2tree area distance keys grid
        {keys=keys; tree=tree}

let findSolution (keynum:int) (solution: Solution) (fullGrid: Map<char,Map<char,Grid>>) : Solution option =
    let mutable solution_queue : queue<Solution> = MyQueue.empty
    solution_queue <- enqueue solution_queue solution
    let mutable mindistance : int option = None
    let mutable alternatives : Solution list = List.empty

    while (MyQueue.length solution_queue > 0) do
        let solution = dequeue &solution_queue
        let solution = {solution with tree = grid2tree solution.tree.area solution.tree.distance solution.keys fullGrid.[solution.tree.area]}
        let branches = solution.tree.branches
        if  (branches = [||] ) then 
            if solution.keys.Length = keynum 
            then updateMin &mindistance &alternatives solution
        else
        match mindistance with
        | Some d when d < solution.tree.distance + (solution.tree.branches |> Array.map (fun t -> t.distance) |> Array.min) -> () 
        | _ ->
        let indexes =
            [|0..branches.Length-1|]
            |> Array.sortBy(fun idx -> ((if isKey branches.[idx].area then 0 else 1) , branches.[idx].distance))
        for i in indexes do
            if branches.[i].area = '#' then 
                failwith "not expected with smart grid" 
            else
            if branches.[i].area = Space then
                failwith "not expected with smart grid"
            else
            if (Char.IsLower branches.[i].area) then
                let solutionNext = next KeyStep i solution fullGrid
                if solutionNext.keys.Length = keynum
                then  updateMin &mindistance &alternatives solutionNext
                else
                solution_queue <- enqueue solution_queue solutionNext
            else
            if (Char.IsUpper branches.[i].area) then
                failwith "not expected with smart grid"
  
    match alternatives with
    | [] -> None
    | alternatives ->
        alternatives |> List.minBy(fun a -> a.tree.distance) |> Some

1 single step receives as input which is the move index i
2 then it updates the distance of the current solution draft by summing the distance to the vertex I
3 it updates the current position as of vertex I
4 it also updates the list of predecessors by including vertex i
5 it computes the new tree of reachable vertices starting from the `fullGrid` and taking into account the newly updated list of predecessors

Notice that this is a constrained version of the TSP where each vertex can have as constraint a list of predecessors.

Start by receiving the graph topology and starting point
    Define a mindistance variable
    and a list of completed solutions, initially empty

    Start looping at the queue of partial solutions
        So a single partial solution is dequeued
        It computes possible vertices based on current predecessors
        Check if nothing remains and adds it to the completed alternatives otherwise updating mindistance
        Otherwise loop as in classical BFS
        For all possible moves = reachable vertices
                
                For each one applies above said single step
                If done updates mindistance and completed alternatives 
                Otherwise enqueue such partial solution 
                
  
    Finally select the min alternative by distance.