adjacency matrix size: 35992
adjacency matrix time:87953ms

"lead" to "gold":
lead, load, goad, gold
search time:219ms

"ruby" to "code"
ruby, rudy, rude, rode, code
search time:125ms

"code" to "ruby"
code, rode, rude, rudy, ruby
search time:110ms

"java" to "code"
java, lava, lana, lane, lone, cone, code
search time:156ms

"sean" to "deck"
sean, bean, beak, beck, deck
search time:141ms

I use a modified version of Dijkstra's shortest path algorithm in conjunction with a pre-calculated adjacency matrix for all the four-letter words. Clearly the adjacency matrix construction takes up the bulk of the time for one search, but if you do multiple searches using the same adjacency matrix then it becomes more effecient overall.

A more interesting variation would be to allow other edges besides single-letter changes. Edges represending the addition or removal of a letter could be incorporated into the adjacency matrix, and those edges given different costs than single-letter change edges. The code that produced the above results assumed all edges had equal costs.

It's Halloween. I think I'll go as a dork.