I have a problem dealing with word ladders. The problem is: given two words and a dictionary file, find the shortest word ladder between the two words. So if given the words cat and pot:
cat -> cot -> pot
That is just an easy example. You get the idea.
The problem is the time constraint, The problem calls for using a graph, which will be really good to use one since the second part of the problem deals with finding the ladder with the least weight.
If I pre-generate the graph (generate the full graph at the program execution) it would take a long long time. Since the algorithm I came up with compared each word to all the other words in the dictionary to find the adjacent nodes. That comes up to O(n^2) comparisons, plus comparing letters of same size words. Which ends up being a lot.
I did a test run with a 1k 3 letter word list and it took 2.6s to generate the graph. That means that with a 200k list it would take 26 hours to generate the graph.
After finding this out I thought about generating a graph starting only from the starting word and then finding all the adjacent nodes(words that are only a letter different) and then all the adjacent nodes for the previous adjacent nodes until the end word is found, or if its not found then there would be no path.
The programming language is C++. Is there a more efficient algorithm I could use for this?