CODEWITHSUNDEEP
javashortest-pathbreadth-first-search
user2001375
user2001375

Reputation: 89

How to find the shortest path in a maze using breadth first search?

I realise this question has been asked several times but I'm just trying to understand how to put it into context. I'm trying to figure out how to find the shortest path in a maze using breadth first search. I've been given a program which creates a maze, I'm trying to find the shortest path through it.

package solver;

import java.awt.Point;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BreadthFirstSearch extends AbstractSolver {  

    @Override
    public List<Point> solve(int[][] maze, Point start, Point goal) {
        LinkedList<Point> path = new LinkedList<Point>();
        List<Point> prevPoints = new LinkedList<Point>();
        Queue<Point> agenda = new LinkedList<Point>();
        List<Point> visited = new LinkedList<Point>();

        agenda.add(start);
        visited.add(start);

        while(!agenda.isEmpty()) {
            Point current = agenda.remove();

            for(Point neighbour : getNeighbours(current, maze)) {
                if(!visited.contains(neighbour)) {

                    visited.add(neighbour);
                    agenda.add(neighbour);

                }
            }
        }
        return null;
    }

}

I'm trying to figure out away to connect the parent node to the children, so that I can trace the connection back to the start Point and return the path.

Upvotes: 0

Views: 1447

Answers (1)

Flying_Banana
Flying_Banana

Reputation: 2910

Breadth-first search is probably not the most efficient way to find the shortest path (See Dijkstra's shortest path algorithm). But if you insist, I suppose you would want to create a list for every possible configuration of paths, then select the shortest one.

Of course, that will be a LOT of paths! What you can do is implement your own Dijkstra's algorithm based on bfs (which, really, is based on bfs to begin with). This roughly entails creating your own class of points and add a field called next which points to your next point, as well as each time you visit an unexplored point, you update the shortest path to that point. For details, just visit the wiki or search it up on Youtube (Wikipedia can be hard to understand at times, but the pseudo code there is very useful ;)!

Upvotes: 1

Related Questions