A shortest path connects two graph nodes with the fewest total steps or lowest cost. In a word ladder, each word is a node and each valid one-step transformation is an edge; every edge has equal cost. section 5.1.1
A word-ladder program can approach the task incrementally:
- Read the starting and ending words. section 5.1.1
- Build a graph from a dictionary, connecting words reachable in one valid step. section 5.1.1
- Search the graph for the shortest path between the two words. section 5.1.1
Cat to dog
The chain cat → hat → heat → heal → held → dole → does → dogs → dog is valid but longer than cat → cats → tags → goat → got → dog, making the second chain a shortest solution among the examples. section 5.1.1
Figure 5.2 A ladder graph for a selection of English words
Use the ladder-graph figure to inspect how words become nodes and valid transformations become connecting edges. section 5.1.1
