Solved: Find shortest path on graph with 1 character difference


I have a somewhat complicated question. I am provided a list of words (each word has the same length). I am given two words into my function (StartNode and EndNode) and my task is to find the shortest path between the two (A follow-up would be how to collect all paths from startNode to EndNode). The words can only be connected if they have at most a 1 word difference. For example, TRIE and TREE could be connected since they only differ by one letter (I v E) but TRIE and TWEP can’t be connected since they have 2 character differences.
My solution was to first build an adjacency list, which I successfully implemented, and then compute a BFS to determine whether a path exists between the startNode and endNode. I am able to determine if a path exists but I’m unsure on how I can keep track of the path.
My attempt is as follows:
My BFS doesn’t take in the path and the total_length is quite obviously wrong too. Is there any way I can improve my algorithm?
Sample Input:
Expected Output:
Current Output:
Any tips on where I am going wrong?

Best Answer:

For anyone who stumbled upon this question, I did figure out a solution. A normal BFS just figures out if a path exists to the node and implicitly goes through the shortest traversal BUT if you want to show that traversal (path or length of path), it becomes necessary to keep two more counters.
In this case, I kept a counter of predecessor and a distance from source, my function therefore becomes:
When the BFS is complete, we will also have a pred and distance array set up. Predecessor would contain each node and its predecessor in the path from start -> end (and -1 if no connection exists). To print out the path from start-> end, we could use a helper function.
Additionally, I also kept the distance dictionary. It would show the path to each node.
Helper Function:
This is kind of a Djikstra’s algorithm approach but I’m unsure on how else I can achieve this

If you have better answer, please add a comment about this, thank you!