# Java Shortest Path solution

• My solution is based on find the shortest path in a weighted directed graph, first we construct the graph base on the following concept:

``````if a/c = 2.0 then there are two nodes a and c, we will have the following edges:
there is an edge from a to c and its weight is 2.0
there is an edge from c to a and its weight is 0.5
there is an edge from a to a and c to c and their weight are both 1.0
``````

note every edge's length is 1, just their weight are different. For each query, we just need to calculate the shortest path from dividend to divisor, and get the product of the weight of the edges in the path.

``````public class Solution {
static HashMap<String,Integer> dist;
public static double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
int equationsCount = equations.length;
int queriesCount = queries.length;
double[] res = new double[queriesCount];
HashMap<String,Boolean> visit = new HashMap<String,Boolean>();
HashMap<String,HashMap<String,Double>> graph = new HashMap<String,HashMap<String,Double>>();
if(equationsCount == 0) return res;

for(int i = 0; i < equationsCount; i++){ //construct the graph
HashMap<String,Double> tmp;
if(!graph.containsKey(equations[i][0])){
tmp = new HashMap<String,Double>();
tmp.put(equations[i][0],1.0);
}else{
tmp = graph.get(equations[i][0]);
}
tmp.put(equations[i][1],values[i]);
graph.put(equations[i][0],tmp);

if(!graph.containsKey(equations[i][1])){
tmp = new HashMap<String,Double>();
tmp.put(equations[i][1],1.0);
}else{
tmp = graph.get(equations[i][1]);
}
tmp.put(equations[i][0],1.0/values[i]);
graph.put(equations[i][1],tmp);

visit.put(equations[i][1],false);
visit.put(equations[i][0],false);
}

for(int i = 0; i < queriesCount; i++){
if(graph.containsKey(queries[i][0]) && graph.containsKey(queries[i][1])){
if(queries[i][0].equals(queries[i][1])) {
res[i] = 1.0;
continue;
}
dist = new HashMap<String,Integer>();
HashMap<String,Boolean> visitCopy = new HashMap<String,Boolean>(visit);
BFS(queries[i][1],graph,visitCopy,dist);
visitCopy = new HashMap<String,Boolean>(visit);
boolean find = false;
res[i] = 1.0;
while(!queue.isEmpty()){ //find shortest path
String cur = queue.removeFirst();
visitCopy.put(cur,true);
int min = Integer.MAX_VALUE;
String next = "";
for(String nxt : graph.get(cur).keySet()){
if(!visitCopy.get(nxt) && dist.get(nxt) < min){
min = dist.get(nxt);
next = nxt;
}
visitCopy.put(nxt,true);
}
if(!next.isEmpty()) {
res[i] *= graph.get(cur).get(next);
if(next.equals(queries[i][1])) {
find = true;
break;
}
}
}
if(!find) res[i] = -1;
}else{
res[i] = -1;
}
}
return res;
}

// calculate distance map using BFS
public static void BFS(String dest, HashMap<String,HashMap<String,Double>> graph, HashMap<String,Boolean> visit, HashMap<String,Integer> dist){

for(String s : graph.keySet()){
if(s.equals(dest)) dist.put(s,0);
else dist.put(s,Integer.MAX_VALUE);
}

while(!queue.isEmpty()){
String current = queue.removeFirst();
visit.put(current,true);
HashMap<String,Double> neighbors = graph.get(current);
for(String key : neighbors.keySet()){
if(!visit.get(key)){
int val = dist.get(key);
val = dist.get(current) + 1;
dist.put(key,val);