Finding the shortest path nodes with breadth first search

by

Storing all the visited nodes in a single list is not helpful for finding the shortest path because in the end you have no way of knowing which nodes were the ones that led to the target node, and which ones were dead ends.

What you need to do is for every node to store the previous node in the path from the starting node.

So, create a map Map<Integer, Integer> parentNodes, and instead of this:

shortestPath.add(nextNode);

do this:

parentNodes.put(unvisitedNode, nextNode);

After you reach the target node, you can traverse that map to find the path back to the starting node:

if(shortestPathFound) {
    List<Integer> shortestPath = new ArrayList<>();
    Integer node = nodeToBeFound;
    while(node != null) {
        shortestPath.add(node)
        node = parentNodes.get(node);
    }
    Collections.reverse(shortestPath);
}

More Related Contents:

  1. Data Structure in Java
  2. Deciding a Big-O notation for an algorithm
  3. How to check if an integer is in a set of given ranges? [closed]
  4. How to detect a loop in a linked list?
  5. Stack with find-min/find-max more efficient than O(n)?
  6. Anagram algorithm in java
  7. Sample Directed Graph and Topological Sort Code [closed]
  8. How to restore the PriorityQueue to its initial state before the method call?
  9. How to determine if binary tree is balanced?
  10. Hash : How does it work internally?
  11. How to implement a Median-heap
  12. The simplest algorithm for poker hand evaluation
  13. Random Number Algorithm – Implementation in Java
  14. Graph theory puzzle about connectivity?
  15. Write a program that takes an array/arraylist of integer and finds longest sub array/arraylist whose entries are equal [closed]
  16. Algorithm to divide a given number in two proportions by one of the component of that number
  17. Java – class, get new array of objects
  18. What’s the best way to build a string of delimited items in Java?
  19. Take n random elements from a List?
  20. JAXB: How should I marshal complex nested data structures?
  21. How to create a 2 way map in java
  22. A better algorithm to find the next palindrome of a number string
  23. All possible combinations of an array
  24. How to find all permutations of a given word in a given text?
  25. What is a non recursive solution for Fibonacci-like sequence in Java?
  26. best way to pick a random subset from a collection?
  27. ArrayList Vs LinkedList
  28. Algorithm for 2D Raytracer
  29. How to acquire a lock by a key
  30. Creating a LinkedList class from scratch

Leave a Comment