When I am checking all possible paths then sometimes I have got a little better result than in tests.
Are the test correct for sure?

It seems so, try printing the input values and see it for yourself.

yes, still possible. That would become a classical path finding problem, and yes, you would have to check all the possible paths (algo: depth first search, breadth first search, best first search, A*, ...).