Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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:

Robot 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.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

So long as you know your starting node (which in this case you do), you can use Dijkstra's Algorithm to find the shortest path. Although you didn't specify if there are weights for the paths, it accounts for that as well so long as there are no negative values allowed in the weights.

This uses the assumption that the robot has some form of memory. It isn't able to see parts of the map that it is not adjacent to, but memorizing the vertices and their weights is a must for any sort of efficient algorithm.

share|improve this answer
    
Haha love how you thought ahead about the weights of the paths. The part one of my problem ignores all weightings and is simply about finding the shortest path. The second part will involve a battery charge (percentage) at each node. But I will create another Question when the time comes. Thank You, I will try coding Dijkstra's Algorithm in Java. –  Ciwan Jan 20 '13 at 13:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.