Background: Here is the scenario, imagine I have a little Robot. I give this robot a Map, and I want him to traverse the map, after doing so, I want the Robot to tell me the shortest possible path on the map. So here is an example of a Map:
Difficulties: The Robot is given the Map in the form of a HashMap. For the above map it will be something like this:
A > B, E
B > A, C, E
C > B, E
D > E
E > A, B, C, D, F
F > E
So node [ A ] has neighbours [ B ] and [ E ] and so on. The Robot can only know the neighbours of the node it is currently at.
So only when at node [ A ] will the Robot know that the neighbours of [ A ] are [ B ] and [ E ]. The Robot has no way of knowing what neighbours [ B ] has unless it is at [ B ], once there, the Robot can call the getNeighbouringNodes() method to find out the neighbours (Returned to Robot as a List).
Current Thinking: At the moment my logic for getting the shortest path from Start to Exit is as follows:
Essentially, it is a breadth first traversal. Once at the start node [ A ], I get the list of neighbouring nodes, then visit first neighbour in the list [ B ].
Once at [ B ] I call the isThisAnExitNode() method to check that [ B ] is an exit node, if yes, write my short path, and exist the map. If no, I go back to node [ A ] and grab the next neighbour of [ A ] which is [ E ].
Do same with [ E ], now if no Exit node was found, I move onto [ B ] to explore its neighbours.
I think you get the idea.
My question is, am I doing it right? Is there a better, more efficient way than my method of traversal?
Any help would be greatly appreciated.
Thank You.
