0

I am brushing up my algorithm and data structure knowledge and was wondering if someone could help me figure out how to find the shortest path between two nodes with BFS. So far I am have the following method, which returns the shortest parth in a graph:

private Node[] nodes;

public static int[] shortestPath(Node source){
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(source);

        int[] distances = new int[totalNodes];
        Arrays.fill(distances,-1);

        distances[source] = 0;

        while(!queue.isEmpty()){
            Node node = queue.poll();

            for (int neighbor: nodes[node].neighbor) {
                if(distances[neighbor] == -1) {
                    distances[neighbor] += distances[distanceIndex] + 1;
                    queue.add(neighbor);
                }

            }
        }
            return distances;
    }


}

I was wondering how would the solution look if I wanted to implement a method like this:

public static int[] shortestPath(Node source, Node destination){
// 
}

Thanks in advance for the help, I am new to data structures and not sure how to go about it

hispanicprogrammer
  • 367
  • 3
  • 6
  • 22
  • this will help https://www.geeksforgeeks.org/shortest-path-unweighted-graph/ – deadshot Aug 04 '20 at 15:35
  • 1
    Just the function stub seems pretty broad. You virtually have the BFS written, why not try moving it into that function stub? Just stop the loop when you hit the destination and rebuild the path using a "came from" hashmap. Many dupes are available, [here's one](https://stackoverflow.com/questions/41789767/finding-the-shortest-path-nodes-with-breadth-first-search). – ggorlen Aug 04 '20 at 15:38

1 Answers1

1
private Node[] nodes;

public static int shortestPath(Node source, Node destination){
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(source);

        int[] distances = new int[totalNodes];
        Arrays.fill(distances,-1);

        distances[source] = 0;

        while(!queue.isEmpty()){
            Node node = queue.poll();

            for (int neighbor: nodes[node].neighbor) {
                if(distances[neighbor] == -1) {
                    distances[neighbor] += distances[node] + 1;
                    queue.add(neighbor);

                    if(neighbor == destination)
                      break;
                }

            }
        }
            return distances[destination];
    }
Amit Rastogi
  • 926
  • 2
  • 12
  • 22