q times BFS; not using Floyd-Warshall


  • 0
    Z
    /**
     * 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);
            }
    
            /*compute answer*/
            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;
    
            Queue<String> q = new LinkedList<>();
            q.add(src);
    
            Set<String> visited = new HashSet<>();
            visited.add(src);
    
            // 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);
    
                // explore adj nodes
                Map<String, Double> adjs = g.get(cur);
                for(String adj: adjs.keySet()){
                    if(!visited.contains(adj)){
                        visited.add(adj); 
    
                        double weight = adjs.get(adj);
                        vals.put(adj, vals.get(cur)* weight);
                        q.add(adj);
                    }
                }
            }
    
            // no path exists.
            return -1.0;
        }
    }

Log in to reply
 

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