But doesn't that require that the algorithm already knows that what are the possible connections between different nodes? I mean, if I just take the [x,y] positions of each ford, it doesn't tell me that to what river branch does which ford belong. Oh, but maybe I have to test this approach too.

I think that I have to make the algorithm so that it has room for many different alternatives and AI to pick a different route according to different criteria. For example, a peaceful fisher going to a lake would prefer the shortest route. But a bunch of raiders might want to avoid open terrains and try to stay hidden, sneaking upon their destination and maybe even choosing a unexpected route...