The problem takes as input the description of a city (graph) and prints the shortest path from source city to destination city.
The challenging part of this problem is that how you want to represent the graph?
Since there are just 26*26 distinct city names you can use adjacency matrix too, but I use adjacency list by using a map of "string" to "vector". I also use a map of "string" to "string" to save the precedence (father) node of another node, so I can print the path easily, and I use a set of "string" to mark nodes that I have visited recently.
And the rest and main part of the problem is to find the shortest path from source city to destination city that I do it using a queue of "string".
No comments:
Post a Comment