My test cases for BFS - Shortest Path challenge are all comin wrong. Here is my code : -
import java.util.Scanner;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.HashMap;
public class Main {
public static void main(String args[]) {
Scanner scn = new Scanner(System.in);
int q = scn.nextInt();
while(q>0){
Graph graph = new Graph();
int n = scn.nextInt();
int m = scn.nextInt();
for(int i=1;i<=n;i++){
graph.addvertex(i);
}
while(m>0){
int a = scn.nextInt();
int b = scn.nextInt();
graph.addedge(a,b,6);
m–;
}
int src = scn.nextInt();
graph.displayshortest(src);
System.out.println();
q–;
}
}
}
class Graph{
private class Vertex{
HashMap<Integer,Integer> nbrs = new HashMap<>();
}
HashMap<Integer,Vertex> vtces;
Graph(){
vtces = new HashMap<>();
}
public int numvertex(){
return this.vtces.size();
}
public boolean containsvertex(Integer vname){
return this.vtces.containsKey(vname);
}
public void addvertex(Integer vname){
if(vtces.containsKey(vname)){
return;
}
Vertex vtx = new Vertex();
vtces.put(vname,vtx);
}
public void removevertex(Integer vname){
Vertex vtx = vtces.get(vname);
ArrayList keys = new ArrayList<>(vtx.nbrs.keySet());
for(Integer key : keys){
Vertex nbrvtx = vtces.get(key);
nbrvtx.nbrs.remove(vname);
}
}
public int numedges(){
int count=0;
ArrayList keys = new ArrayList<>(vtces.keySet());
for(Integer key : keys){
Vertex vtx = vtces.get(key);
count+=vtx.nbrs.size();
}
return count/2;
}
public boolean containsedge(Integer vname1,Integer vname2){
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null||vtx2==null||!vtx1.nbrs.containsKey(vname2)){
return false;
}
return true;
}
public void addedge(Integer vname1,Integer vname2,int cost){
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null||vtx2==null||vtx1.nbrs.containsKey(vname2)){
return;
}
vtx1.nbrs.put(vname2,cost);
vtx2.nbrs.put(vname1,cost);
}
public void removeedge(Integer vname1,Integer vname2){
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null||vtx2==null||!vtx1.nbrs.containsKey(vname2)){
return;
}
vtx1.nbrs.remove(vname2);
vtx2.nbrs.remove(vname1);
}
public void display(){
ArrayList keys = new ArrayList<>(vtces.keySet());
for(Integer key : keys){
Vertex vtx = vtces.get(key);
System.out.println(key + " : “+ vtx.nbrs);
}
}
public void displayshortest(Integer src){
ArrayList keys = new ArrayList<>(vtces.keySet());
for(Integer key : keys){
if(key!=src){
if(!bfs(src,key)){
System.out.print(”-1"+" “);
}
}
}
}
private class Pair{
Integer vname;
Integer psf;
}
public boolean bfs(Integer src,Integer dst){
HashMap<Integer,Boolean> processed = new HashMap<>();
LinkedList queue = new LinkedList<>();
Pair sp = new Pair();
sp.vname=src;
sp.psf=0;
queue.addLast(sp);
while(!queue.isEmpty()){
Pair rp = queue.removeFirst();
if(processed.containsKey(rp.vname)){
continue;
}
processed.put(rp.vname,true);
if(containsedge(rp.vname,dst)){
System.out.print(rp.psf+6+” ");
return true;
}
Vertex rpvtx = vtces.get(rp.vname);
ArrayList nbrs = new ArrayList<>(rpvtx.nbrs.keySet());
for(Integer nbr : nbrs){
if(!processed.containsKey(nbr)){
Pair np = new Pair();
np.vname=nbr;
np.psf=rp.psf+6;
queue.addLast(np);
}
}
}
return false;
}
}
Please clarify how to correct it.
BFS - Shortest Path challenge all test cases wrong
@sanchit02,
I see that you have got a correct answer in the question. Do you have any further doubts?
Yeah I got the code correct somehow. No I do not have any further doubts 
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.