Finding the shortest path in the maze

Question

I am an amateur programmer who is learning to program. I have never had courses in computer science, so I had difficulties with this trivial problem:

class Room { String name; ArrayList<Room> neighbors = new ArrayList<Room>(); // constructor with name // getters void addNeighbor(Room room) { neighbors.add(room); } } class Finder { void findShortestPath(Room start, Room end) { // ? } } 

Each room has several neighbors. More than 4, so this does not look like a matrix-oriented problem. You are given the final room, and you must find the shortest path from the start room (comparing the names of the rooms). The result should be a “way” as follows:

Start: Kitchen

End: Toilet

Way: Kitchen, Living room, Hallway, Bedroom, Toilet.

I think I should use some recursion for the rooms, and I think I should save, where I was already in some kind of stack. But I do not know how to start.

Can some of you guys help me? Thanks

Answer 1

You are looking for BFS .

In your case, the graph G = (V,E) is actually V= { all rooms } and E = {(u,v), (v,u) | u and v are neighboring rooms } E = {(u,v), (v,u) | u and v are neighboring rooms }

Note that it doesn’t matter to you that before running the algorithm, not all edges [neighbors] - you know how to calculate the corresponding set of edges [and rooms] on the fly using the neighbors field. This is true because each “edge” that you need to use for your path was “discovered” when you discovered a room that is closer to the path to the source.

You can look at this post - how you can find the actual path after starting BFS.

Answer 2

You want to write a width search. There are many resources in this thread.