Floyd算法

这个实际上就是动态规划, 转移方程为dp(i, j) = dp(i,k) + dp(k,j). parent(i, j) = parent[k][j]; 算法复杂度 n^3, 空间复杂度 N^2.

正确性保证的原因是dp[i][j]的最短路一定由两部分组成, dp[i][k] 和 dp[k][j], 这两部分一定代表了最短路.

举个复杂的例子, dp(i, x)开始由dp(i, k1)+dp(k1, k2)+dp(k2 ,x)组成. 而真正的最短路径由 dp(i, k3) + dp(k3, k4) + dp(k4, k2) + dp[k2, x] 组成. 尽管一开始k2是第一个被我们用来当中转update的, 可是到后来我们用k3先update了dp(i, k4)的最小值, 用k4做中转的时候, dp(i, k4) (在中转k3)的时候算过了, dp(k4, x) (在中转k2)的时候算过了, 当前用 dp(i, k4)+dp(k4, x)可以算出dp(i, x)的最小值.

Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）

  从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis\(i,j\)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis\(i,k\) + Dis\(k,j\) < Dis\(i,j\)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis\(i,j\) = Dis\(i,k\) + Dis\(k,j\)，这样一来，当我们遍历完所有节点k，Dis\(i,j\)中记录的便是i到j的最短路径的距离。

2).算法描述：

a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

3).Floyd算法过程矩阵的计算----十字交叉法

方法：两条线，从左上角开始计算一直到右下角 如下所示

给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点

Evaluate Division

对原题进行见图, 见图时自己指向自己时, set value 1.0. 更新时用mid做连乘. 注意这题不是算最小值, 图不一定是全连接, 找src和dst时只要找和mid相连的. 效率不高. 这个可能和query的数量有关.

public class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        HashMap<String, HashMap<String, Double>> map = new HashMap<String, HashMap<String, Double>>();
        int count = 0;
        for(String[] e : equations){
            if(!map.containsKey(e[0])) {
                map.put(e[0], new HashMap<String, Double>());

            }
            if(!map.containsKey(e[1])) {
                map.put(e[1], new HashMap<String, Double>());
            }
            map.get(e[0]).put(e[0], 1.0);
            map.get(e[1]).put(e[1], 1.0);
            map.get(e[0]).put(e[1], values[count]);
            map.get(e[1]).put(e[0], 1.0/values[count]);

            count++;
        }


        for(String mid : map.keySet()){
            for(String start : map.get(mid).keySet())
                for(String end: map.get(mid).keySet()){
                    double val = map.get(start).get(mid)*map.get(mid).get(end);
                    map.get(start).put(end, val);
                }
        }

        double[] ans = new double[queries.length];
        for(int i=0;i<ans.length;i++){
            String[] e = queries[i];
            if(!map.containsKey(e[0]) || !map.get(e[0]).containsKey(e[1]))
                ans[i]=-1.0;
            else
                ans[i] = map.get(e[0]).get(e[1]);
        }
        return ans;
    }
}

另一种方法是在建图后用dfs(start, end)的方式来完成query. 这个代码比较笨拙, 建立了两个hashmap

public class Solution {
    public double[] calcEquation(String[][] equations, double[] value, String[][] queries) {
        HashMap<String, ArrayList<String>> pairs = new HashMap<String, ArrayList<String>>();
        HashMap<String, ArrayList<Double>> values = new HashMap<String, ArrayList<Double>>();

        for(int i=0;i<equations.length;i++){
            String[] equation = equations[i];
            if(!pairs.containsKey(equations[i][0])){
                pairs.put(equations[i][0], new ArrayList<String>());
                values.put(equations[i][0], new ArrayList<Double>());
            }

            if(!pairs.containsKey(equations[i][1])){
                pairs.put(equations[i][1], new ArrayList<String>());
                values.put(equations[i][1], new ArrayList<Double>());
            }
            pairs.get(equation[0]).add(equation[1]);
            values.get(equation[0]).add(value[i]);
            pairs.get(equation[1]).add(equation[0]);
            values.get(equation[1]).add(1.0/value[i]);
        }
        double[] ans = new double[queries.length];
        for(int i=0;i<queries.length;i++){
            HashSet<String> visited = new HashSet<String>();
            ans[i] = dfs(pairs, values, visited, queries[i][0], queries[i][1], 1.0);
            if(ans[i]==Double.MAX_VALUE)
                ans[i]=-1.0;
        }
        return ans;
    }

    public double dfs(HashMap<String, ArrayList<String>> pairs, HashMap<String, ArrayList<Double>> values, 
                HashSet<String> visited, String start, String end, double cur){
        if(visited.contains(start) || !pairs.containsKey(start))
            return Double.MAX_VALUE;
        if(start.equals(end))
            return cur;

        visited.add(start);
        ArrayList<String> neighbors = pairs.get(start);
        for(int i=0;i<neighbors.size();i++){
            double tmp = dfs(pairs, values, visited, neighbors.get(i),end, cur*values.get(start).get(i));
            if(tmp!=Double.MAX_VALUE){
                return tmp;
            }
        }
        visited.remove(start);
        return Double.MAX_VALUE;
    }
}

Friend Circles

这道题解法很多, 三种解法

• Union Find
• DFS/BFS, 对第二层元素maintain visited set
• Floyd, 对第二层元素maintain visited set

这题floyd也能解决. 利用floyd来传递连通性, 这道题因为定义了就两层friends, direct和indirect, 所以可以再用简单的枚举解决. Floyd还是复杂度太高, beat 1.81%

public class Solution {
    public int findCircleNum(int[][] M) {
        int n = M.length;
        for(int k=0;k<n;k++)
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++){
                    M[i][j] = M[i][j] | (M[i][k] & M[k][j]);
                }

        HashSet<Integer> visited = new HashSet<Integer>(); int count = 0;
        for(int i=0;i<n;i++){
            if(!visited.contains(i)){
                count++;
                for(int j=0;j<n;j++)
                    if(M[i][j]==1)
                        visited.add(j);
            }
        }
        return count;
    }
}