Java Shortest Path solution


  • 0
    O

    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;
                    LinkedList<String> queue = new LinkedList<String>();
                    queue.add(queries[i][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()) {
                            queue.add(next);
                            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){
    
            LinkedList<String> queue = new LinkedList<String>();
            queue.add(dest);
            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);
                        queue.add(key);
                        visit.put(key,true);
                    }
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.