How do I use Breadth First Search to output the shortest path and not just tell me there is a path?

Viewed 1635

Im trying to create a program where i can add nodes and use a LinkedList to connect them. Once I have these connected nodes, I wanted to find the shortest path between them using Breadth First Search. Currently my program only finds whether of not there is a path, but i want to know what that path is. How should i modify my code?

public static boolean findPath(String start, String destination){
            //find the nodes given the String key
            Node current = getNode(start);
            Node end = getNode(destination);

            //create a linked list to store the visited nodes
            LinkedList<Node> nextToVisit = new LinkedList<Node>();
            HashSet<Node> visited= new HashSet<Node>();
            nextToVisit.add(current);
            while(!nextToVisit.isEmpty()){
                Node node = nextToVisit.remove();
                System.out.println(node.name);
                if(node == end)
                    return true;
                if(visited.contains(node))
                    continue;
                visited.add(node);
                for(Node children : node.adjacent){
                    nextToVisit.add(children);
                }
            }
            return false;
        }
3 Answers
Related