java solution using Floyd–Warshall algorithm


  • 10
    F

    Using a variant of Floyd–Warshall algorithm, to find the distance between each reachable pair:

        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
            Function<String, HashMap<String, Double>> function = s -> new HashMap<>();
            for (int i = 0; i < equations.length; i++) {
                graph.computeIfAbsent(equations[i][0], function).put(equations[i][0], 1.0);
                graph.computeIfAbsent(equations[i][1], function).put(equations[i][1], 1.0);
                graph.get(equations[i][0]).put(equations[i][1], values[i]);
                graph.get(equations[i][1]).put(equations[i][0], 1 / values[i]);
            }
            for (String mid : graph.keySet()) {
                for (String src : graph.get(mid).keySet()) {
                    for (String dst : graph.get(mid).keySet()) {
                        double val = graph.get(src).get(mid) * graph.get(mid).get(dst);
                        graph.get(src).put(dst, val);
                    }
                }
            }
            double[] result = new double[queries.length];
            for (int i = 0; i < result.length; i++) {
                if (!graph.containsKey(queries[i][0])) {
                    result[i] = -1;
                } else {
                    result[i] = graph.get(queries[i][0]).getOrDefault(queries[i][1], -1.0);
                }
            }
            return result;
        }
    

    It is very slow, some optimization applied:

        public double[] calcEquation2(String[][] equations, double[] values, String[][] queries) {
            HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
            for (int i = 0; i < equations.length; i++) {
                String src = equations[i][0], dst = equations[i][1];
                if (!graph.containsKey(src)) {
                    graph.put(src, new HashMap<>());
                }
                if (!graph.containsKey(dst)) {
                    graph.put(dst, new HashMap<>());
                }
                graph.get(src).put(src, 1.0);
                graph.get(dst).put(dst, 1.0);
                graph.get(src).put(dst, values[i]);
                graph.get(dst).put(src, 1 / values[i]);
            }
            for (String mid : graph.keySet()) {
                for (String src : graph.get(mid).keySet()) {
                    for (String dst : graph.get(mid).keySet()) {
                        double val = graph.get(src).get(mid) * graph.get(mid).get(dst);
                        graph.get(src).put(dst, val);
                    }
                }
            }
            double[] result = new double[queries.length];
            for (int i = 0; i < result.length; i++) {
                if (!graph.containsKey(queries[i][0])) {
                    result[i] = -1;
                } else {
                    result[i] = graph.get(queries[i][0]).getOrDefault(queries[i][1], -1.0);
                }
            }
            return result;
        }
    

    In practice, we can use guava's HashBasedTable, do not have to use HashMap<String,HashMap<String,Double>>,:

    import com.google.common.collect.HashBasedTable;
    import com.google.common.collect.Table;
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            Table<String, String, Double> table = HashBasedTable.create();
            for (int i = 0; i < equations.length; i++) {
                String src = equations[i][0], dst = equations[i][1];
                table.put(src, src, 1.0);
                table.put(dst, dst, 1.0);
                table.put(src, dst, values[i]);
                table.put(dst, src, 1.0 / values[i]);
            }
            for (String mid : table.rowKeySet()) {
                for (String src : table.row(mid).keySet()) {
                    for (String dst : table.row(mid).keySet()) {
                        double val = table.get(src, mid) * table.get(mid, dst);
                        table.put(src, dst, val);
                    }
                }
            }
            double[] result = new double[queries.length];
            for (int i = 0; i < queries.length; i++) {
                result[i] = table.contains(queries[i][0], queries[i][1]) ? table.get(queries[i][0], queries[i][1]) : -1.0;
            }
            return result;
        }
    

  • 0
    S

    Good work. Amazing!


  • 0
    L

    @fhqplzj I did not understand what optimization you made other than removing the Function and computeIfAbsent part?


  • 0
    F

    @leetrocks Yes, functional programming in java is very slow


  • 0
    L

    @fhqplzj Thanks for your response. In your inner two for loops, do you know why are you computing values only for the pairs (src and dst) which are the children of the intermediate node (mid) ? Why not for other pairs which are not the children of mid? In Floyd Warshall, we compute for all pairs for all intermediate nodes.


  • 0
    M

    @leetrocks I have the same question. Can some one pls answer.


  • 1
    J

    The Floyd-Warshall compares all the pairs to calculate the minimum distance, but in this particular problem, there is one and only one distance for each valid pair, or if a path is found, it is the shortest path. So there is no need to visit all other pairs to update the distance, its suffice to just iterate thorough connected nodes.


Log in to reply
 

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