Let' s build a set of all reachable states

(Subscript[p, 12])[{m1_,m2_,m3_}]:={Max[m1-(3-m2),0],Min[m1+m2,3],m3} 
(Subscript[p, 13])[{m1_,m2_,m3_}]:={Max[m1-(8-m3),0],m2,Min[m1+m3,8]}
(Subscript[p, 21])[{m1_,m2_,m3_}]:={Min[m2+m1,5],Max[m2-(5-m1),0],m3}
(Subscript[p, 23])[{m1_,m2_,m3_}]:={m1,Max[m2-(8-m3),0],Min[m2+m3,8]}
(Subscript[p, 31])[{m1_,m2_,m3_}]:={Min[m1+m3,5],m2,Max[m3-(5-m1),0]}
(Subscript[p, 32])[{m1_,m2_,m3_}]:={m1,Min[m2+m3,3],Max[m3-(3-m2),0]}

it[0]:={{0,0,8}}
it[n_]:=Union@Flatten[Table[(Subscript[p, i])[j],{j,it[n-1]},{i,{12,13,23,21,32,31}}],1]

it[4]

Table[Intersection[Flatten@it[n],{4}],{n,1,10}]

Thus, the minimal number of steps needed to have a state where one of the jugs contain 4 liters is six.

Union@it[6]

It remains to find the path between {0,0,8} and {4,3,1}.

Quit[]

Let’s list the edges (note that there is no need to generate the set of vertices to generate a connected graph, but they help with the construction of the sets of edges).

(Subscript[v, i_])[{m1_,m2_,m3_}]:={m1,m2,m3}->(Subscript[p, i])[{m1,m2,m3}]
ve[n_]:=Union@Flatten@Table[(Subscript[v, i])[j],{j,it[n-1]},{i,{12,13,21,23,31,32}}]

ve[2]

Let' s remove the loops.

clean[n_]:=Table[i-> i,{i,it[n]}]

g=Graph[Complement[ve[6],clean[6]],VertexLabels->"Name"]

FindShortestPath[g,{0,0,8},{4,3,1}]

Let' s do this again adding a spilling jug.

(Subscript[sp, 12])[{m1_,m2_,m3_,m4_}]:={Max[m1-(3-m2),0],Min[m1+m2,3],m3,m4} 
(Subscript[sp, 13])[{m1_,m2_,m3_,m4_}]:={Max[m1-(8-m3),0],m2,Min[m1+m3,8],m4}
(Subscript[sp, 21])[{m1_,m2_,m3_,m4_}]:={Min[m2+m1,5],Max[m2-(5-m1),0],m3,m4}
(Subscript[sp, 23])[{m1_,m2_,m3_,m4_}]:={m1,Max[m2-(8-m3),0],Min[m2+m3,8],m4}
(Subscript[sp, 31])[{m1_,m2_,m3_,m4_}]:={Min[m1+m3,5],m2,Max[m3-(5-m1),0],m4}
(Subscript[sp, 32])[{m1_,m2_,m3_,m4_}]:={m1,Min[m2+m3,3],Max[m3-(3-m2),0],m4}
(Subscript[sp, 41])[{m1_,m2_,m3_,m4_}]:={Min[m4+m1,5],m2,m3,Max[m4-(5-m1),0]}
(Subscript[sp, 42])[{m1_,m2_,m3_,m4_}]:={m1,Min[m4+m2,3],m3,Max[m4-(3-m2),0]}
(Subscript[sp, 43])[{m1_,m2_,m3_,m4_}]:={m1,m2,Min[m4+m3,8],Max[m4-(8-m3),0]}
(Subscript[sp, 14])[{m1_,m2_,m3_,m4_}]:={0,m2,m3,m1+m4}
(Subscript[sp, 24])[{m1_,m2_,m3_,m4_}]:={m1,0,m3,m2+m4}
(Subscript[sp, 34])[{m1_,m2_,m3_,m4_}]:={m1,m2,0,m3+m4}

sit[0]:={{0,0,8,0}}
sit[n_]:=Union@Flatten[Table[(Subscript[sp, i])[j],{j,it[n-1]},{i,{12,13,23,21,32,31,41,42,43,14,24,34}}],1]

sit[3]

Table[Intersection[Flatten@sit[n],{4}],{n,1,6}]

So allowing spilling does not make the problem any easier to solve.