[数据结构与算法]必会算法总结5—弗洛伊德算法

必会算法总结(5) - 弗洛伊德算法

? 弗洛伊德算法又是一个图论的算法，可能有小伙伴会问，会这么多图论的算法有用吗？可以说这对于校招进大厂的小伙伴是特别重要的，而且图相对于其它的数据结构是比较复杂的，现在的笔试动不动就是一道基于图去实现的题，可以说图论算法成了进大厂的第一步，所以我们必须特别重视图论算法的设计与实现。

? 回到正题，上一篇我们讲解的迪杰斯特拉算法广泛适用于单源最短路径问题，而弗洛伊德算法则更广泛的适用于多源最短路径问题，因为它用到了动态规划的思路去求解，所以避免了重复计算。各位要区分清除一个算法所解决的问题域。写这篇博客的时候我看大多数人都是用邻接矩阵去实现弗洛伊德算法，那么这里我给出基于邻接表的实现方式。

算法核心

弗洛伊德算法的核心在于二维矩阵shortest，它存储两个节点之间的最小距离。有了这个shortest矩阵，若shortest[i][j] > shortest[i][k] + shortest[k][j]，则需要更新shortest[i][j]

图的存储结构

这里我选用图的邻接表存储形式：

• Node类

  public class Node {
      int value;
      Map<Node, Integer> neighbors;
      
      public Node() {}
      
      public Node(int value) {
          this.value = value;
      }
      
      public Node(int value, Map<Node, Integer> neighbors) {
          this.value = value;
          this.neighbors = neighbors;
      }
  }
  

• Graph类

  public class Graph {
      List<Node> nodes;
      
      public Graph() {}
      
      public Graph(List<Node> nodes) {
          this.nodes = nodes;
      }
  }
  

算法核心

public Map<Node, Map<Node, Integer>> shortestPath(Graph graph) {
    // 创建最短距离矩阵：shortest
    Map<Node, Map<Node, Integer>> shortest = new TreeMap<>();
    // 初始化最短距离矩阵
    for (Node node : graph.nodes) {
        shortest.put(node, new TreeMap<>(node.neighbors));
        shortest.get(node).put(node, 0);
    }
    // 弗洛伊德算法核心
    for (Node k : graph.nodes) { // 选择中间节点k
        for (Node i : graph.nodes) { // 选择起始节点i
            for (Node j : graph.nodes) { // 选择终止节点j
                if (i != j && i != k && j != k
                        && shortest.get(i).containsKey(k)
                        && shortest.get(k).containsKey(j)) {
                    // 更新最小值
                    shortest.get(i).put(j, Math.min(
                            shortest.get(i).getOrDefault(j, Integer.MAX_VALUE),
                            shortest.get(i).get(k) + shortest.get(k).get(j)
                    ));
                }
            }
        }
    }
    return shortest;
}

算法总结

下面的代码是上面的汇总并附带了一个实例：

public class Main {
    
    static class Node {
        int value;
        Map<Node, Integer> neighbors;

        public Node() {}

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Map<Node, Integer> neighbors) {
            this.value = value;
            this.neighbors = neighbors;
        }
	}
    
    static class Graph {
        List<Node> nodes;

        public Graph() {}

        public Graph(List<Node> nodes) {
            this.nodes = nodes;
        }
	}
    
    public Map<Node, Map<Node, Integer>> shortestPath(Graph graph) {
        // 创建最短距离矩阵：shortest
        Map<Node, Map<Node, Integer>> shortest = new TreeMap<>();
        // 初始化最短距离矩阵
        for (Node node : graph.nodes) {
            shortest.put(node, new TreeMap<>(node.neighbors));
            shortest.get(node).put(node, 0);
        }
        // 弗洛伊德算法核心
        for (Node k : graph.nodes) { // 选择中间节点k
            for (Node i : graph.nodes) { // 选择起始节点i
                for (Node j : graph.nodes) { // 选择终止节点j
                    if (i != j && i != k && j != k
                            && shortest.get(i).containsKey(k)
                            && shortest.get(k).containsKey(j)) {
                        // 更新最小值
                        shortest.get(i).put(j, Math.min(
                                shortest.get(i).getOrDefault(j, Integer.MAX_VALUE),
                                shortest.get(i).get(k) + shortest.get(k).get(j)
                        ));
                    }
                }
            }
        }
        return shortest;
	}
    
	public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        node1.neighbors = new HashMap<>();
        node2.neighbors = new HashMap<>();
        node3.neighbors = new HashMap<>();
        node4.neighbors = new HashMap<>();

        node1.neighbors.put(node2, 5);
        node1.neighbors.put(node4, 7);
        node2.neighbors.put(node3, 4);
        node2.neighbors.put(node4, 2);
        node3.neighbors.put(node1, 3);
        node3.neighbors.put(node2, 3);
        node3.neighbors.put(node4, 2);
        node4.neighbors.put(node3, 1);

        Graph graph = new Graph(
            new ArrayList<>(Arrays.asList(node1, node2, node3, node4)));

        shortestPath(graph).forEach((k, v) -> System.out.printf("%s -- %s\n", k, v));
    }
    
}