As I said, my algorithm is probably not that good in this szenario

It could be made somewhat feasible if I pregenerated a database of all the shortest paths between any 2 words (together with all letters used and the points it awards). That would be 4000x4000 = 16 million entries

But with all the testing and optimizing that would be the work of a few days, which I don't have at the moment. Sorry