# q times BFS; not using Floyd-Warshall

• ``````/**
* Floyd-Warshall : all pair shortest path. RT O(V^3) SP O(V^2) , therefore not gonna use this.
* =====
* Gonna use BFS or DFS for graph traversal. q * O(E + V) ; if q > V then all-pair shortest path is better.
* Looking for path bwtween 2 nodes.
*/
public class Solution {
public double[] calcEquation(String[][] es, double[] vs, String[][] qs) {
/*build map*/
Map<String, Map<String, Double>> g = new HashMap<>();
for(int i=0; i < es.length; i ++){
String s = es[i][0];
String e = es[i][1];
double val = vs[i];

// add 2 edges with inversed weights
g.computeIfAbsent(s, k -> new HashMap<>()).put(e,val);
g.computeIfAbsent(e, k -> new HashMap<>()).put(s,1/val);
}

double[] ans = new double[qs.length];
for(int i =0; i < qs.length; i ++){
ans[i] = find(g, qs[i][0], qs[i][1]);
}

return ans;
}

/**
* BFS dst examine path existance between s and e. Keep myltiplying on the way.
* return -1 if no path found.
*/
double find(Map<String, Map<String, Double>> g, String src, String dst){
/*if input src or dst not in the graph, return -1.0*/
if(!g.containsKey(src) || !g.containsKey(dst))
return -1.0;

Set<String> visited = new HashSet<>();

// dst -> multiplied weight, on path between src and dst
Map<String, Double> vals = new HashMap<>();
vals.put(src, 1.0);

/*bfs loop*/
while(!q.isEmpty()){
String cur = q.poll();
if(cur.equals(dst)) // reached the destination
return vals.get(dst);