Can you measure the distance and the work needed to cross the fords?

Trying all the routes you have two choices: depth first search and breadth first search. In depth first you go as far as you can until you find the goal or get stuck in dead end. In breadth first search you check all the possibilities at hand before you advance. The latter uses lot of memory and the first can go in an eternal loop.

The first idea would be to memorize the passed fords and avoid one that you've passed already. If it's possible.

If you know you can get some solution in tolerable time and you can measure how long you've gone already, a branch and bound algorithm would be a good choice. Find the goal and measure the distance (counting the work crossing the fords) and save it as the best solution. Then go on again in backtracking (when all possibilities from this point are exhausted, go back to the previous point and try other available routes if there are any) but every time you've gone as far as your present best solution, go back because there are no better routes ahead.) If you find a better route, save it as the best route and go on until you find an optimum.

Again if you want to avoid loops and you can keep track of the distance you've gone, one choice that combines depth first and breadth first is iterative deepening search that wastes a bit of computing resources but essentially works as breadth first but uses as little memory as depth first. On the other hand, in iterative deepening you have to know some good guesses about how long you're going.

Iterative deepening goes like this: For simplicity's sake let's assume the distances are simple integers. First try all the solutions with distance 1, then solutions of distance 2 etc. Eventually the first route you'll find will be the shortest one.

I'm not sure what you need but hope this helps.