CODEWITHSUNDEEP
javashortest-pathbreadth-first-search
hm1233
hm1233

Reputation: 25

ShortestPath with BFS (BreadthFirstSearch)

I am trying to return the shortest path between two vertices for a graph. I have a code written to find the breadthFirstSearch but I do not know how to modify it to make it return the shortest path. Below is my breadthFirstSearch function

private void breadthFirstSearch(T start,T end){

    Queue<T> queue = new LinkedList<>();
    Set<T> visited = new HashSet<>();
    visited.add(start);
    queue.add(start);
    while(!queue.isEmpty()){
        T v = queue.poll();
            for(int i =0;i<this.keyToVertex.get(v).successors.size();i++){                  if(visited.contains(this.keyToVertex.get(v).successors.get(i).key)){ 
                continue;
            }
            visited.add(this.keyToVertex.get(v).successors.get(i).key);
            queue.add(this.keyToVertex.get(v).successors.get(i).key);
        }

    }       

}

So how can I modify it to return the shortestpath.

Upvotes: 1

Views: 99

Answers (1)

janos
janos

Reputation: 124804

You need to track in Queue more than just a value to check, but the path leading to that value. So the type should be more than just Queue<T> but for example Queue<LinkedList<T>>.

The first value in the queue should the singleton list of start instead of just start.

As you process the values in the queue, vertex you're visiting will be the last element of the queue item, and when you add an item to the queue, it should be a clone of the current item, with the next neighbor added.

Something like this:

Queue<LinkedList<T>> queue = new LinkedList<>();
queue.add(new LinkedList<>(Collections.singleton(start)));

while (!queue.isEmpty()) {
    LinkedList<T> path = queue.poll();
    T v = path.getLast();
    if (v.equals(end)) {
        return path;
    }

    for (int i = 0; i < this.keyToVertex.get(v).successors.size(); i++) {
        T v2 = this.keyToVertex.get(v).successors.get(i).key;
        if (visited.contains(v2)) {
            continue;
        }

        LinkedList<T> path2 = new LinkedList<>(path);
        path2.add(v2);
        queue.add(path2);
        visited.add(v2);
    }
}

Upvotes: 1

Related Questions