How to solve this with simple forward-backward algorithm?

I've been playing around with the forward-backward algorithm to find the most efficient (determined by a cost function dependent on how a current state differs from the next state) path to go from State 1 to State N. In the picture below, a short version of the problem can be seen with just 3 States and 2 Nodes per State. I do forward-backward algorithm on that and find the best path like normal. The red bits in the pictures are the paths checked during forward propagation bit in the code.

Now the interesting bit, I now want to find the best 3-State Length path (as before) but now only Nodes in the first State are known. The other 4 are now free-floating and can be considered to be in any State (State 2 or State 3). I want to know if you guys have a good idea of how to do this.

Picture: https://i.sstatic.net/TJZg8.jpg

Note: Bear in mind the original problem consists of around 25 States and 100 Nodes per State. So, you'll know the State of around 100 Nodes in State 1 but the other 24*100 Nodes are Stateless. In this case, I want find a 25-State length path (with minimum cost).

Addendum: Someone pointed out a better algorithm would be Viterbi's algorithm. So here is a problem with more variables thrown in. Can you guys explain how would that be implemented? Same rules apply, the path should start from one of the Nodes in State 1 (Node a or Node b). Also, the cost function using the norm doesn't make sense in this case since we only have one property (Size of node) but in the actual problem I'm expecting a lot more properties.

A variation of Dijkstra's algorithm might be faster for your problem than the forward-backward algorithm, because it does not analyze all nodes at once. Dijkstra is a DP algorithm after all.

Let a node be specified by

Node:
   Predecessor : Node
   Total cost : Number      
   Visited nodes : Set of nodes  (e.g. a hash set or other performant set)

Initialize the algorithm with

open set : ordered (by total cost) set of nodes = set of possible start nodes (set visitedNodes to the one-element set with the current node)
           ( = {a, b} in your example)

Then execute the algorithm:

do
    n := pop element from open set
    if(n.visitedNodes.count == stepTarget)
        we're done, backtrace the path from this node
    else
        for each n2 in available nodes
            if not n2 in n.visitedNodes
                push copy of n2 to open set (the same node might appear multiple times in the set):
                    .cost := n.totalCost + norm(n2 - n)
                    .visitedNodes := n.visitedNodes u { n2 }  //u = set union
                    .predecessor := n                    
        next
loop

If calculating the norm is expensive, you might want to calculate it on demand and store it in a map.