BFS - Shortest Path Java

justformyntra8 · June 28, 2019, 1:46pm

I am getting timed out error for this code:
Lemme know how to optimize it:

bhardwaj-aman/java-data-structures-practice-questions/blob/master/graphs/BFSGraph

package GraphPractice;
import  java.util.*;

public class Graph {
   static Scanner s = new Scanner(System.in);
    private class vertex{
        HashMap<String ,Integer> neighbours;
        vertex(){
            neighbours = new  HashMap<String ,Integer>();
        }
    }
    HashMap<String,vertex> vertices;
    Graph(){
        vertices = new HashMap<String, vertex>();
    }
    public int numvertex(){
        return vertices.size();
    }
    public boolean containsvertex(String a){
        for(String x:vertices.keySet()){

This file has been truncated. show original

Ariba_Parveen · July 1, 2019, 11:22am

Use HashMap to store your ans . So that you can access the elements in O(1) .

justformyntra8 · July 1, 2019, 7:37pm

that’s exactly what i’ve done.

Ariba_Parveen · July 1, 2019, 10:22pm

You should use bfs function in which src node is passed as a parameter and a hashmap is returned containing the shortest paths as key and minimum distance as value from given source vertex to all the vertices . After that you can print the value part of hashmap except for the source vertex.